心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

被这道水题郁闷了好久,就像脑子转不过来一样,大致思路有,但是一直不懂得如何实现。
Last(x)表示顺时针方向x位置的上一个有效位置;
Next(x)表示顺时针方向x位置的下一个有效位置(x位置的数字允许已经被删除);
下面的代码中,即使只剩下一个元素也允许调用Last(x)、Next(x),因为此时x位置的数字已经删除,Last(x)、Next(x)将返回仅剩的一个元素的位置;但是不存在元素的时候要及时break循环,否则调用Last(x)、Next(x)会死循环。最初就是这点没有反应过来,写了许多if来判断各种情况,越写越复杂。
以下是我的代码:

#include<cstdio>
using namespace std;
const int kMaxn(27);

int n,k,m,cnt;
int r[kMaxn];
bool sign[kMaxn];

int Last(int pos)
{
    
int i(pos-1);
    
if(i<1)
        i
=n;
    
while(!r[i])
    {
        i
--;
        
if(i<1)
            i
=n;
    }
    
return i;
}
int Next(int pos)
{
    
int i(pos+1);
    
if(i>n)
        i
=1;
    
while(!r[i])
    {
        i
++;
        
if(i>n)
            i
=1;
    }
    
return i;
}

int main()
{
    
/*
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    //
*/

    
while(scanf("%d%d%d",&n,&k,&m)==3 && (n || k ||m))
    {
        
for(int i=1;i<=n;i++)
        {
            r[i]
=i;
            sign[i]
=false;
        }

        
int i(n),j(1),ans[kMaxn];
        cnt
=0;
        
while(true)
        {
            
for(int v=1;v<=k;v++)
                i
=Next(i);
            
for(int v=1;v<=m;v++)
                j
=Last(j);
            
if(i==j)
            {
                cnt
++;
                ans[cnt]
=r[i];
                
if(cnt<n)
                    sign[cnt]
=true;
                
if(cnt>=n)
                    
break;
                r[i]
=0;
                i
=Last(i);
                j
=Next(j);
            }
            
else
            {
                cnt
++;
                ans[cnt]
=r[i];
                cnt
++;
                ans[cnt]
=r[j];
                
if(cnt<n)
                    sign[cnt]
=true;
                
if(cnt>=n)
                    
break;
                r[i]
=r[j]=0;
                i
=Last(i);
                j
=Next(j);
            }
        }

        
for(int i=1;i<=n;i++)
        {
            printf(
"%3d",ans[i]);
            
if(sign[i])
                printf(
",");
        }
        printf(
"\n");
    }

    
return 0;
}
posted on 2011-04-13 20:46 lee1r 阅读(492) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:基础/模拟题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理