1249: 士兵队列训练问题

2021-4-09
http://tjuacm.chaosheng.top/problem.php?id=1249
http://acm.hdu.edu.cn/showproblem.php?pid=1276
这个题测试用例输出的一样但是WA。
更新：发现原因了，问题出在3个数的排序，它满足样例，但是输入4顺序就不对了。
再次更新！不是顺序问题，是对题目的理解有问题。他是每次都要出队都要从第一个测试到最后一个，而不是达到三个就结束！！所以输入4得到的不是1 3 4而是1 3。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5000;
//bool out[N];


int main(){
    int n, m;
    cin >> n;
    while(n--){
        cin >> m;
        queue<int> num;
        for(int i = 0; i < m; i++){
            num.push(i);
        }
        int casen = 0;
        int t = 0;
        while(num.size() > 3){
            int tmp = num.front();
            t++;
            if(tmp == 1){
                t = 1;
                casen++;
                num.pop();
                num.push(tmp);
            }else{
                if(casen % 2 == 1 && t % 2 == 0){  //报数2 
                    num.pop();    
                }else if(casen % 2 == 0 && t % 3 == 0){ //报数3 
                    num.pop();
                }else{
                    num.pop();
                    num.push(tmp);
                }
            }
        }
        int tmp = num.front();
        num.pop();
        num.push(tmp);

        //输出第一个 
        cout << num.front(); 
        num.pop();
        while(!num.empty()){
            cout << " " << num.front();
            num.pop(); 
        }
        cout << endl;
    }

    return 0;
}

更改后的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5000;
int ans[3];


int main(){
    int n, m;
    cin >> n;
    while(n--){
        cin >> m;
        queue<int> num;
        for(int i = 1; i <= m; i++){
            num.push(i);
        }
        int casen = 1;          
        while(num.size() > 3){
            int x = num.size(); //当前人数 
            if(casen % 2 == 1){     //2
                for(int i = 0; i < x/2; i++){
                    num.push(num.front()); //把第奇数个数压回队列 
                    num.pop();             //把第奇数个数弹出 
                    num.pop();             //把第偶数个数回队列  
                }
                if(x % 2 == 1){  //剩最后一个没有回到队尾 
                    num.push(num.front());
                    num.pop();
                } 
            }else{
                for(int i = 0; i < x/3; i++){
                    num.push(num.front()); //把第1数个数压回队列 
                    num.pop();             //把第1数个数弹出 
                    num.push(num.front()); //把第2数个数压回队列 
                    num.pop();             //第2个数弹出
                    num.pop();             //第3个数弹出  
                }
                while(x % 3 != 0){  //最后有数没有回到队尾 
                    num.push(num.front());
                    num.pop();
                    x--; 
                } 
            } 
            casen++;
        }
        while(num.size() != 1){
            printf("%d ", num.front());
            num.pop();
        }
        printf("%d\n", num.front());
        num.pop();
    }

    return 0;
}

2021-5-17
自己再写了一次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5010;

queue<int> q;

int main(){
    int t, n, m;
    cin >> t;
    while(t--){
        cin >> n;
        //while(!q.empty()) q.pop();
        queue<int> q;
        for(int i = 1; i <= n; i++){
            q.push(i);
        }

        int way = 0;
        int k;
        while(q.size() > 3){
            int len = q.size();
            if(way % 2 == 0){
                k = 1;
                while(k <= len){
                    if(k % 2 == 0){
                        q.pop();
                    }else{
                        int tmp = q.front();
                        q.pop();
                        q.push(tmp);
                    }
                    k++;
                }
            }
            if(way % 2 == 1){
                k = 1;
                while(k <= len){
                    if(k % 3 == 0){
                        q.pop();
                    }else{
                        int tmp = q.front();
                        q.pop();
                        q.push(tmp);
                    }
                    k++;
                }
            }
            way++;
        }

        while(q.size() != 1){
            cout << q.front() << " ";
            q.pop();
        }
        cout <<q.front() << endl;
    }
    return 0;
}