2thweek.training.c。链表典型题

题意：

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

Input

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

Sample Input

2 20 40

Output

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

分析及思路：

一开始是直接用的链表解决，将士兵人数为1、2的情况单列出来。士兵数大于三时用其编号除以二，编号恰能整除2的元素剔除出链表，判断一次士兵人数是否不小于三。如果是接着将重新组成的链表的编号能整除3的元素剔除，然后再次判断新的链表的元素人数是否不小于三。。。。。。

可是由于对链表和迭代器应用不熟悉，程序怎么改都输不出案列答案。

失败代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<list>
 4 #include<algorithm>
 5 using namespace std;
 6 int main()
 7 {
 8     int N,i;
 9     scanf("%d",&N);
10     while(N--)
11     {
12         int n;
13         list<int>a;
14         while(scanf("%d",&n)==1 && n<=5000)
15         {
16 
17         for(i=1;i<=n;i++)
18         {
19 
20             a.push_back(i);
21         
22 
23         }
24         }
25 
26 
27         list<int>::iterator it,ip;
28         int s=a.size();
29         while(s==1||s==2)
30         {
31             printf("%d",a.front());
32         }
33 
34        while(s>=3)
35        {
36            for(it=a.begin();it!=a.end();  )
37             {
38                 if((*it)%2==0)
39                 {
40                    //ip=it;
41                    a.erase(it);
42                    it++;
43                    s--;
44                 }
45             else  ip=it;
46             }
47 
48        }
49        while(s>=3)
50        {
51                 for(it=a.begin();it!=a.end(); )
52                 {
53                     if((*it)%3==0)
54                     {   // ip=it;
55                         a.erase(it);
56                         it++;
57                         s--;
58                     }
59                      else  ip=it;
60                 }
61 
62 
63        }
64 
65 
66        for(it=a.begin();it!=a.end();it++)
67 
68         //if(it==a.end())
69         //printf("%d",a.end());
70        //else
71         printf("%d ",(*it));
72 
73        printf("%d",a.end());
74     }
75 
76        return 0;
77 }

代码留此目的是为了再次过来修改，以待重新用链表的方法完成。

当时参考了大神的代码和旁边的童鞋的意见，觉得直接用模拟也方便。代码如下：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6     int a[5002];
 7     int t,n,m;
 8     int i,j,k;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%d",&n);
13         for(i=0;i<n;i++)    //存储士兵编号
14             a[i]=i+1;
15         m=n;
16         k=0;
17         while(m>3)  //人数大于3，继续报数删人
18         {
19             j=0;
20             k=0;
21             for(i=0;i<m;i++)
22             {
23                 j++;
24                 if(j==2)    //报数为2，士兵出列
25                 {
26                     a[i]=5004;  //出列者编号设为最大值，排序后直接屏蔽，避免下次搜索超时 觉得这样简直忒好，不是真的直接剔除元素，
                                  //     也就无需考虑后面的删除第三个人的序号问题
27                     j=0;
28                     k++;   //k为出列人数
29                 }
30             }
31            sort(a,a+m);        //     一轮报数完成，士兵排序站队，屏蔽已报数士兵
32             m-=k;
33             j=0;
34             if(m<=3)        //    人数不大于3，停止报数删人
35                 break;
36             k=0;
37             for(i=0;i<m;i++)
38             {
39                 j++;
40                 if(j==3)
41                 {
42                     a[i]=5004;
43                     j=0;
44                     k++;
45                 }
46             }
47             sort(a,a+m);    //一轮报数完成，士兵排序站队，屏蔽已报数士兵
48             m-=k;
49         }
50         printf("%d",a[0]);
51         for(i=1;i<m;i++)
52             printf(" %d",a[i]);
53         puts("");
54     }
55     return 0;
56 }

小抱怨：对于链表队列真是把我愁了，有点分不清楚。只好拿着大神的代码模仿又模仿。等搞清楚定要回头重写一番。大家都很厉害真的很是沮丧。学姐告诉我：全世界的光明也不能剥夺一支小蜡烛发亮的权利，全世界的黑暗也不能一支小蜡烛失去光辉！或许自己的进步微不足道也不要轻易放弃，要知道未来真的在路上在手上在不断运转的大脑里。