首页 > 代码库 > uva 11995 I Can Guess the Data Structure!
uva 11995 I Can Guess the Data Structure!
There is a bag-like data structure, supporting two operations: 1 x Throw an element x into the bag. 2 Take out an element from the bag. Given a sequence of operations with return values, you’re going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine! Input There are several test cases. Each test case begins with a line containing a single integer n (1 ≤ n ≤ 1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). Output For each test case, output one of the following: stack It’s definitely a stack. queue It’s definitely a queue. priority queue It’s definitely a priority queue. impossible It can’t be a stack, a queue or a priority queue. not sure It can be more than one of the three data structures mentioned above.
Sample Input
6 1 1 1 2 1 3 2 1 2 2 2 3 6 1 1 1 2 1 3 2 3 2 2 2 1 2 1 1 2 2 4 1 2 1 1 2 1 2 2 7 1 2 1 5 1 1 1 3 2 5 1 4 2 4
Sample Output
queue not sure impossible stack priority queue
————————————————————我是分割线——————————————————
纯模拟题目。
祝大家都ak愉快。
1 /* 2 Problem: 3 OJ: 4 User: S.B.S. 5 Time: 6 Memory: 7 Length: 8 */ 9 #include<bits/stdc++.h>10 #include<iostream>11 #include<cstdio>12 #include<cstring>13 #include<cmath>14 #include<algorithm>15 #include<queue>16 #include<cstdlib>17 #include<iomanip>18 #include<cassert>19 #include<climits>20 #include<functional>21 #include<stack>22 #include<bitset>23 #include<vector>24 #include<list>25 #define F(i,j,k) for(int i=j;i<k;++i)26 #define M(a,b) memset(a,b,sizeof(a))27 #define FF(i,j,k) for(int i=j;i>=k;i--)28 #define maxn 1000129 #define inf 0x3f3f3f3f30 #define maxm 400131 #define mod 99824435332 #define LOCAL33 using namespace std;34 int read(){35 int x=0,f=1;char ch=getchar();36 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}37 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}38 return x*f;39 }40 int n,m;41 struct POINT42 {43 int id;44 int data;45 friend bool operator < (POINT a,POINT b){return a.data < b.data;}46 }d[maxn];47 inline bool pdstk()48 {49 stack<int> stk;50 F(i,0,n){51 if(d[i].id==1) stk.push(d[i].data);52 if(d[i].id==2){53 if(stk.empty()) return false;54 if(stk.top()==d[i].data){stk.pop();continue;}55 else return false;56 }57 }58 return true;59 }60 inline bool pdque()61 {62 queue<int> q;63 F(i,0,n){64 if(d[i].id==1) q.push(d[i].data);65 if(d[i].id==2){66 if(q.empty()) return false;67 if (q.front()==d[i].data){q.pop();continue;}68 else return 0;69 }70 }71 return true;72 }73 inline bool pdheap()74 {75 priority_queue<POINT> h;76 F(i,0,n){77 if (d[i].id==1) h.push(d[i]);78 if(d[i].id==2){79 if(h.empty()) return false;80 if(h.top().data=http://www.mamicode.com/=d[i].data){h.pop();continue;}81 else return 0;82 }83 }84 return true;85 }86 int main()87 {88 std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;89 #ifdef LOCAL90 freopen("qu.in","r",stdin);91 freopen("qu.out","w",stdout);92 #endif93 cin>>n;94 F(i,0,n) cin>>d[i].id>>d[i].data;95 if(pdstk()) cout<<"YES"<<endl;else cout<<"No"<<endl;96 if(pdque()) cout<<"YES"<<endl;else cout<<"No"<<endl;97 if(pdheap()) cout<<"YES"<<endl;else cout<<"No"<<endl;98 return 0;99 }
uva 11995 I Can Guess the Data Structure!