首页 > 代码库 > HDU-1276

HDU-1276

题目描述:

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

 

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

 

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

 

Sample Input
2 20 40
 

 

Sample Output
1 7 19 1 19 37

 

 

代码如下:

 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,n,sol_num,cnt;
    int sol[5005];
    //输入数据的组数;
    cin>>n;
    while(n--){
        //每次都需要把数组清零;
        memset(sol,0,sizeof(sol));
        //输入新兵的人数;
        cin>>sol_num;
        //把初始编号存入数组;
        for(int i=1;i<=sol_num;i++)  sol[i]=i;
        //把变量sol_num用作每次筛选剩下的人数;
        N=sol_num;
        //剩下的人数不超过3个;
        while(sol_num>3){
            cnt=0;
            //当人数不超过3个的时候跳出
            if(sol_num>3){
                //每次都循环到N;
                for(int i=1;i<=N;i++){
                    //跳过被赋值为另的位置;
                    if(sol[i])  cnt++;
                    //把报数为2的赋值为0,当前长度减1;
                    if(cnt==2){
                        sol[i]=0;
                        sol_num--;
                        cnt=0;
                    }
                }
            }
            cnt=0;
            //当人数不超过三个的时候跳出;
            if(sol_num>3){
                for(int i=1;i<=N;i++){
                    if(sol[i])  cnt++;
                    if(cnt==3){
                        sol[i]=0;
                        sol_num--;
                        cnt=0;
                    }
                }
            }
        }
        //输出的时候注意控制空格,为零的位置要直接跳过;
        int tmp=0;
        for(int i=1;i<=N;i++){
            if(sol[i]!=0){
                if(tmp==1)  cout<<" ";
                tmp=1;
                cout<<sol[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

该题思想来自网络;

HDU-1276