这道题就是典型的有优先队列
以不一样的标准排序,还有经常性了插入和删除
如果是优先队列,就是按照x由大到小排序;队列,按标号由小到大;栈,按标号有大到小。
注意:一定要考虑到当出栈大于入栈的情况,这样是impossible,而只有入栈没有出栈是not sure;入栈大于出栈或者等于出栈都是正常处理的
考虑周全
代码:
#include <queue> #include <cstdio> using namespace std; struct pri_q { int x; bool operator < ( const pri_q& a) const { return x < a.x; } }pri; struct stac { int x, i; bool operator < ( const stac& a ) const { return i < a.i; } }sta; struct que { int x, i; bool operator < ( const que& a ) const { return i > a.i; } }qu; bool vis[3]; int main() { int n, op, num, ans, x1, x2; while ( scanf("%d", &n) != EOF ) { ans = 3, x1 = x2 = 0; priority_queue <pri_q> pq1; priority_queue <stac> pq2; priority_queue <que> pq3; vis[0] = vis[1] = vis[2] = 0; for ( int i = 0; i < n; ++i ) { scanf("%d%d", &op, &num); if ( op == 1 ) { x1++; if ( !vis[0] ) pri.x = num, pq1.push(pri); if ( !vis[1] ) sta.x = num, sta.i = i, pq2.push(sta); if ( !vis[2] ) qu.x = num, qu.i = i, pq3.push(qu); } else if ( op == 2 ) { x2++; if ( !pq1.empty() ) { pri = pq1.top(); pq1.pop(); if ( pri.x != num ) vis[0] = true; } if ( !pq2.empty() ) { sta = pq2.top(); pq2.pop(); if ( sta.x != num ) vis[1] = true; } if ( !pq3.empty() ) { qu = pq3.top(); pq3.pop(); if ( qu.x != num ) vis[2] = true; } } } for ( int i = 0; i < 3; ++i ) if ( vis[i] ) ans--; if ( ans < 1 || x2 > x1 ) printf("impossible\n"); else if ( ans > 1 ) printf("not sure\n"); else if ( !vis[0] ) printf("priority queue\n"); else if ( !vis[1] ) printf("stack\n"); else if ( !vis[2] ) printf("queue\n"); } }