本文主要是介绍codeforces 420-C. Okabe and Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你n个数还有2*n个指令，当遇到add的时候就把当前的数压入栈顶中，当遇到remove的时候去除栈顶的数，但是这里有一个限制就是在取出栈顶数的时候，要按照1-n的顺序取出数，所以在取出一些数的时候要重新排列栈里的元素，问你按照顺序取出1-n最少需要重新排列栈里的元素几次
思路：每当遇到一个remove的时候我们就看离他最近的一个add压入栈里的数是不是需要取出的数，如果是需要取出的数直接让该数出栈，如果不是我们就重新排列一次，取出需要取出的数，这个时候我们是把数按照循序放入一个优先队列里面，后add的数先出队列，这样我们在重新排列一次之后就把队列清空，这样就可以保证排列的次数最少。
代码如下：
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>using namespace std;
struct point
{int value;int pos;point (int a,int b){value=a;pos=b;}point() {}bool operator<(point p1)const{return pos<p1.pos;}
};
int main()
{int n;int cur=1;int ans=0;int f=0;scanf("%d",&n);int nn=0;priority_queue<point> p;for(int i=0; i<2*n; i++){string order;int x;cin>>order;if(order=="add"){cin>>x;f=0;nn++;p.push(point(x,nn));}if(order=="remove"){if(p.empty()){cur++;continue;}point temp=p.top();if(f){cur++;continue;}else{if(temp.value==cur){cur++;p.pop();}else{ans++;cur++;f=1;while(!p.empty()){p.pop();}}}}}cout<<ans<<endl;return 0;
}
这篇关于codeforces 420-C. Okabe and Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
