1051 Pop Sequence (25 分)
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.
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.
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO是有点恶心这题, 但是还是挺不错的一道题。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 stack<
int>
st;
5 int n,m,k;
6 int an[
1005];
7
8 int main(){
9 cin >> n >> m >>
k;
10 for(
int i =
0; i < k; i ++
){
11 bool flag =
true;
12 for(
int j =
0; j < m; j ++
){
13 cin >>
an[j];
14 }
15 while(!
st.empty()){
16 st.pop();
17 }
18 int p =
1;
19 for(
int l =
0; l < m; l++
){
20 if(p >
m){
21 flag =
false;
22 break;
23 }
24 // cout << p << endl;
25 if(an[l] !=
p){
26 st.push(p++
);
27 // p++;
28 if(st.size() >
n){
29 flag =
false;
30 break;
31 }
32 l--
;
33 }
else{
34 st.push(p++
);
35 if(st.size() >
n){
36 flag =
false;
37 break;
38 }
39 while(!st.empty() && (l < m) && (an[l] ==
st.top())){
40 // cout << st.top();
41 st.pop();
42 l++
;
43 }
44 // if(st.empty())
45 l--
;
46 }
47 }
48 if(!
st.empty()){
49 flag =
false;
50 }
51 if(flag)
52 cout <<
"YES" <<
endl;
53 else
54 cout <<
"NO" <<
endl;
55 }
56 return 0;
57 }
转载于:https://www.cnblogs.com/zllwxm123/p/11185496.html
相关资源:各显卡算力对照表!