HDU1276 - 士兵队列训练问题

Task

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

Input

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

Output

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

Sample

input:

output:

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;
}

文章目录

Task

Input

Output

Sample

Solution