士兵队列训练问题

时间: 1ms        内存:128M

描述:

       某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数。。。,以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止(必须当前报数结束)。

比如10个人,最后剩下的是1和7

输入:

      本题有多个测试数据组,第一行为组数N,接着为N行新兵人数,新兵人数不超过5000。

输出:

      共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。

示例输入:

2
20
40

示例输出:

1 7 19
1 19 37

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
int main()
{
    int N,n,m,i,t,cnt,cnt1;
    scanf("%d",&N);
    while(N>0)
    {
        scanf("%d",&n);
        int a[n];
        for(i=0;i<n;i++)
            a[i]=0;
        m=n;
        cnt=0;
        while(m>3)
        {
            cnt++;
            if(cnt%2==1)
                t=2;
            else if(cnt%2==0)
                t=3;
            cnt1=0;
            for(i=0;i<n;i++)
            {
                if(a[i]==0)
                {
                    cnt1++;
                    if(cnt1%t==0)
                    {
                        a[i]=1;
                        m--;
                    }
                }
            }
        }
        for(i=0;i<n;i++)
            if(a[i]==0)
                printf("%d ",i+1);
        printf("\n");
        N--;
    }
    return 0;
}

参考答案(时间最优[42]):

#include<stdio.h>
#include<string.h>

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,lef;
        int a[5000];
        int i,k;
        scanf("%d",&n);
        lef=n;
        memset(a,1,n*sizeof(int));
        while(lef>3)
        {
            k=0;
            for(i=0;i<n;i++)
            {
                if(a[i])
                    k++;
                if(k==2)
                {
                    k=0;
                    a[i]=0;
                    lef--;
                }
            }
            if(lef<=3)
                break;
            k=0;
            for(i=0;i<n;i++)
            {
                if(a[i])
                    k++;
                if(k==3)
                {
                    k=0;
                    a[i]=0;
                    lef--;
                }
            }
        }
        for(i=0;i<n;i++)
            if(a[i])
                printf("%d ",i+1);
        printf("\n");
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。