用链表实现杭电1276士兵队列训练问题

士兵队列训练问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8554 Accepted Submission(s): 3809

Problem Description

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

Input

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

Output

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

Sample Input

2 20 40

Sample Output

1 7 19 1 19 37

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1276

该题需要注意n<=3的情况：

当n=1时输出1；

当n=2时输出1 2；

当n=3时输出1 2 3；

 1 #include<stdio.h>
 2 
 3 typedef struct node{
 4     int date;
 5     struct node *next;
 6 }*LinkList;
 7 
 8 LinkList Buile(int n);
 9 void delNextNode(LinkList p);
10 int Find(LinkList head, int m, int k);
11 void CountOff(int n);
12 
13 int main()
14 {
15     int i, N, n;
16     scanf("%d", &N);
17     while(N--){
18         scanf("%d", &n);
19         if(n <= 3){
20             printf("1");
21             for(i = 2; i <= n; i++)
22                 printf(" %d", i);
23             printf("
");
24             continue;
25         }
26         CountOff(n);
27     }
28     return 0;
29 }
30 void CountOff(int n)
31 {
32     int k = 2;
33     LinkList head, p;
34     head = Buile(n);
35     while(1){
36         if(k == 2)
37             k = 1;
38         else
39             k = 2;
40         n = Find(head, n, k);
41         if(n <= 3)
42             break;
43     }
44 
45     p = head->next;
46     while(p){
47         if(k){
48             printf("%d", p->date);
49             k = 0;
50         }
51         else
52             printf(" %d", p->date);
53         p = p->next;
54     }
55     printf("
");
56 }
57 LinkList Buile(int n)
58 {
59     LinkList rear, p, head = new node;
60     rear = head;
61     for(int i = 1; i <= n; i++){
62         p = new node;
63         p->date = i;
64         rear->next = p;
65         rear = p;
66     }
67     rear->next = NULL;
68     return head;
69 }
70 void DelNextNode(LinkList p)
71 {
72     LinkList pre;
73     pre = p->next;
74     p->next = pre->next;
75     delete pre;
76 }
77 int Find(LinkList head, int m, int k)
78 {
79     int i;
80     LinkList pre = head;
81     while(pre){
82         i = k;
83         while(i--){
84             if(pre == NULL)
85                 return m;
86             pre = pre->next;
87         }
88         if(!pre || pre->next == NULL)
89             return m;
90         DelNextNode(pre);
91         m--;
92     }
93     return m;
94 }