士兵队列训练问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7307 Accepted Submission(s): 3332

Problem Description

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

Input

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

Output

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

Sample Input

2
20
40

Sample Output

1 7 19
1 19 37

Author

Cai Minglun

Source

杭电ACM集训队训练赛（VI）

Recommend

lcy | We have carefully selected several similar problems for you: 1282 1279 1274 1201 1237

用模拟瞎写的，讲道理应该用队列或者栈来写。。。注意特判，否则会WA

#include <iostream>
#include <cstring>
using namespace std;

int a[5050];
int re(int n)
{
    int k=0;
    for(int i=1;i<=n;i++)
        if(a[i]!=0) k++;
    return k;
}
int main()
{
    int t;
    cin>>t;
    while(t–)
    {
        memset(a,0,sizeof(a));
        int n,flag=0;
        cin>>n;
        if(n<=3)
        {
            cout<<1;
            for(int i=2;i<=n;i++)
                cout<<’ ‘<<i;
            cout<<endl;
            continue;
        }
        for(int i=1;i<=n;i++)
            a[i]=1;
        while(re(n)>3)
        {
            if(flag==0)
            {
                int flag2=0;
                for(int i=1;i<=n;i++)
                {
                    if(a[i-1]==1 && a[i]==1)
                    {
                        a[i]=0;
                        flag2=0;
                    }
                    else if(a[i-1]==0 && a[i]==1 && flag2==1)
                    {
                        a[i]=0;
                        flag2=0;
                    }
                    else if(a[i-1]==0 && a[i]==1 && flag2==0)
                        flag2=1;
                }
                flag=1;
            }
            else
            {
                int flag2=0;
                for(int i=1;i<=n;i++)
                {
                    if(a[i-1]==0 && a[i]==1 && flag2==2)
                    {
                        a[i]=0;
                        flag2=0;
                    }
                    else if(a[i-1]==0 && a[i]==1 && flag2==0)
                        flag2=1;
                    else if(a[i-1]==0 && a[i]==1 && flag2==1)
                        flag2=2;
                }
                flag=0;
            }
        }
        cout<<1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]==1)
                cout<<’ ‘<<i;
        }
        cout<<endl;
    }
    return 0;
}