用一个vector 模拟栈

每次检查输入，如果大于上次出栈的检查是否满足范围要求。满足的话将中间的数压栈

如果小于上次出栈的检查是否为栈尾。满足的话最后一个数出栈

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 51 2 3 4 5 6 73 2 1 7 5 6 47 6 5 4 3 2 15 6 4 3 7 2 11 7 6 5 4 3 2

Sample Output:

YESNONOYESNO

---

来源： <>

 

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. vector<int> inStack;
7. int mark[1010];
9. int main(void) {
10. int n,m,k;
11. cin >> m >> n >> k;
12. for (int j = 0; j < k; j++) {
13. int temp, maxPush = 0;
15. bool flag = true;
16. inStack.clear();
17. for (int i = 0; i < 1002; i++) {
18. mark[i] = 0;
19. }
20. cin >> temp;maxPush = temp;
21. mark[temp]++;
22. if (temp > m || temp < 0)
23. flag = false;
24. for (int i = 1; i < temp; i++) {
25. inStack.push_back(i);
26. mark[i] = 1;
27. }
28. for (int i = 1; i < n; i++) {
29. int lastpop = temp;
30. cin >> temp;
31. mark[temp]++;
32. if (temp > n || temp < 1)
33. flag = false;
35. if (temp <= maxPush + m - inStack.size() && temp>lastpop) {
36. if (temp > maxPush)
37. maxPush = temp;
38. for (int q = lastpop + 1; q < temp; q++) {
39. if(mark[q]==0)
40. inStack.push_back(q);
41. mark[q]++;
42. }
43. }
45. else if (inStack.size()>0&&temp == inStack[inStack.size()-1]) {
46. inStack.pop_back();
47. }
48. else {
49. flag = false;
50. }
51. }
53. if (flag == true)
54. cout << "YES" << endl;
55. else
56. cout << "NO" << endl;
57. }
59. return 0;
61. }