题目：

　　有n个杀手排成一行，每个杀手都有一个不同的编号（编号1-n），在每个夜晚，杀手都会行动，如果某个杀手编号大于他右边的杀手的编号，他就会杀死他右边的杀手，杀手的行动是瞬间的，因此一个人可能某一个夜晚既杀死了别人，又被别人杀死，例如3,2,1这个顺序，在第一个夜晚2会杀死1，同时，3会杀死2，显而易见，一段时间后，就不会有人被杀系，平安夜就到来了，请问在平安夜之前有多少个夜晚。

输入：

　　输入第一行是一个整数n（1<=n<=100000），表示杀手的数量；

　　接下来一行有n个数，是一个1-n的全排列。

输出：

　　输出包好一个整数，表示平安夜之前经历了多少个夜晚；

样例输入：

　　10

　　10　　9　　 7　　8　　6　　5　　3　　4　　2　　1

样例输出：

　　2

样例解释：

　　杀手额变化为：[10 9 7 8 6 5 3 4 2 1]---->[10 8 4]---->[10]，所以答案是2

思路：

　　循环判断，左边的杀手大于右边的杀手即将右边的杀手杀死，同时i将杀死的杀手做以记录，用于下一循环的比较左值， 知道某一循环没有人被杀死，循环结束。

实现：

1 #include <bits/stdc++.h> 2 #include <iostream> 3 using namespace std; 4 5 struct Node 6 { 7 int val; 8 Node* next; 9 Node(int vl) : val(vl), next(NULL) {} 10 }; 11 12 int main() 13 { 14 int n, num; 15 cin >> n; 16 cin >> num; 17 Node* head = new Node(num); 18 Node *last = head, *temp; 19 for (int i = 1; i < n; i++) 20 { 21 cin >> num; 22 temp = new Node(num); 23 last->next = temp; 24 last = temp; 25 } 26 27 int killed = 0, ret = 0; 28 do 29 { 30 killed = 0; 31 Node *first = head, *second = head->next; 32 int lastKilled = 0; 33 while (second != NULL) 34 { 35 if (lastKilled != 0) 36 { 37 if (lastKilled > second->val) 38 { 39 lastKilled = second->val; 40 second = second->next; 41 delete first->next; 42 first->next = second; 43 killed++; 44 } 45 else 46 { 47 lastKilled = 0; 48 first = second; 49 second = second->next; 50 } 51 } 52 else if (first->val > second->val) 53 { 54 lastKilled = second->val; 55 second = second->next; 56 delete first->next; 57 first->next = second; 58 killed++; 59 } 60 else 61 { 62 first = second; 63 second = second->next; 64 } 65 } 66 ret++; 67 } while (killed > 0); 68 69 cout << ret - 1; 70 }

 

转载于:https://www.cnblogs.com/TonvyLeeBlogs/p/9607951.html