在世界的东边,有三瓶雪碧。
——laekov
黎大爷为了虐 zhx,给 zhx 出了这样一道题。黎大爷搞了一个数据结构,但
是他没有告诉 zhx 这到底是什么数据结构,我们只知道这是一个数据结构。为了
让 zhx 知道这是什么数据结构,黎大爷制造了很多次的输入和输出操作。每次加
入操作,黎大爷会告诉你他向这个数据结构加入了一个数并告诉你这是多少;每
次取出操作,黎大爷会从数据结构之中取出一个数并告诉这是多少。黎大爷希望
zhx 根据这些操作来判断这是什么数据结构,但是 zhx 觉得这题太难了所以跑路
了,于是黎大爷把这道题扔给了你。
输入格式:
第一行一个整数N代表操作的数目。
接下来N行,每行两个整数opt,v。如果opt = 1,代表黎大爷把v加入了数据
结构;如果opt = 2,代表了黎大爷从数据结构中取出了一个数,值是v。
输出格式:
输出总共三行,第一行代表数据结构是否可能是栈,第二行代表数据结构是
否可能是队列,第三行代表数据结构是否可能大根堆。每一行的结果都只可能是
“YES”或者“NO” 。
输入样例#1:
2
1 1
2 1
输出样例#1:
YES
YES
YES
对于100%的数据,1 ≤ n ≤ 10 3 。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<stack>
6 using namespace std;
7 int ans1,ans2,ans3;//默认是目标数据结构
8 stack<int>s;
9 queue<int>q;
10 priority_queue<int>heap;
11 int main()
12 {
13 int n;
14 cin>>n;
15 for(int i=1;i<=n;i++)
16 {
17 int p,d;
18 cin>>p;
19 if(p==1)
20 {
21 cin>>d;
22 s.push(d);q.push(d);heap.push(d);
23 }
24 else
25 {
26 cin>>d;
27 if(s.size()==0||q.size()==0||heap.size()==0)
28 {
29 cout<<"NO"<<endl;
30 cout<<"NO"<<endl;
31 cout<<"NO"<<endl;
32 return 0;
33 }
34 if(d!=s.top())ans1=1;
35 if(s.size()!=0)
36 s.pop();
37
38 if(d!=q.front())ans2=1;
39 if(q.size()!=0)
40 q.pop();
41
42 if(d!=heap.top())ans3=1;
43 if(heap.size()!=0)
44 heap.pop();
45
46 }
47 }
48 if(ans1==0)
49 cout<<"YES"<<endl;
50 else cout<<"NO"<<endl;
51 if(ans2==0)
52 cout<<"YES"<<endl;
53 else cout<<"NO"<<endl;
54 if(ans3==0)
55 cout<<"YES"<<endl;
56 else cout<<"NO"<<endl;
57 return 0;
58 }