士兵队列训练问题

士兵队列训练问题

时间： 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");
    }
}

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