链接:https://vjudge.net/problem/HDU-1276

Task

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

Input

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

Output

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

Sample

input:

1
2
3
2
20
40

output:

1
2
1 7 19
1 19 37

Solution

要频繁删除元素,应使用链表,c++中实现双向链表的容器是list。对每一个输入n,用emplace_back向链表末尾插入编号做初始化得到长度为n。当链表长度size()大于3时开始一次删除,定义一个flag变量用于指示当前是间隔2删除还是间隔3删除。每一次遍历时用cnt变量被2或3整除来判断这个节点是否需要被删除,需要删除时用erase()方法执行删除。 注意:由于结构是链表,在遍历时宜使用迭代器的++或–操作顺序访问,不宜像数组那样用随机索引,每次随机索引会很慢。 erase的用法:输入一个迭代器,删除这个迭代器并返回原来在其后的迭代器。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<list>
using namespace std;
int main(){
    int N;
    while(scanf("%d",&N)!=EOF){
        while(N--){
            int n;
            scanf("%d",&n);
            list<int> li={};
            for(int i=1; i<n+1; ++i)
                li.emplace_back(i);
            int flag=0;
            while(li.size()>3){
                if(flag==0){
                    auto it=li.begin();
                    for(int cnt=1; it!=li.end(); ++cnt){
                        if(cnt%2==0) it=li.erase(it);
                        else         it++;
                    }
                }
                if(flag==1){
                    auto it=li.begin();
                    for(int cnt=1; it!=li.end(); ++cnt){
                        if(cnt%3==0) it=li.erase(it);
                        else         it++;
                    }
                }
                flag++;
                if(flag>1) flag=0;
            }
            auto it=li.begin();
            for(int i=0; i<li.size()-1; ++i){
                printf("%d ",*it);
                ++it;
            }
            printf("%d\n",*it);
        }
    }
    return 0;
}