题目:http://pat.zju.edu.cn/contests/pat-a-practise/1057
题解:
维护一个小于等于mid的,一个大于mid的两部分,保持小的的大小和大的的大小一致或者比大的多一个,这样mid即小的的最后一个数。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff multiset<int> minm,maxm; stack<int> s; int mid; void adjust() { multiset<int>::iterator it; if(maxm.size()+1<minm.size()) { //如果小的部分大于大的部分,把小的中最大的元素移到大的当中 it=minm.end(); --it; maxm.insert(*it); minm.erase(it); } else if(maxm.size()>minm.size()) { //如果小的部分小于大的部分,把大的中最小的元素移到小的当中 it=maxm.begin(); minm.insert(*it); maxm.erase(it); } if(s.size()>0) { it=minm.end(); --it; mid=*it; } } int main() { char ch[15]; int n; int top,num; multiset<int>::iterator it; mid=-1; scanf("%d",&n); for(; n--;) { scanf("%s",ch); if(strcmp(ch,"Pop")==0) { if(s.size()==0) printf("Invalid\n"); else { top=s.top(); s.pop(); printf("%d\n",top); if(mid>=top) { it=minm.find(top); minm.erase(it); } else { it=maxm.find(top); maxm.erase(it); } adjust();//调整 } } else if(strcmp(ch,"Push")==0) { scanf("%d",&num); if(s.size()==0) { minm.insert(num); mid=num; } else if(num<=mid) minm.insert(num); else maxm.insert(num); s.push(num); adjust();//调整 } else if(strcmp(ch,"PeekMedian")==0) { if(s.size()==0) printf("Invalid\n"); else printf("%d\n",mid); } else//If the command is invalid, print "Invalid" instead. printf("Invalid\n"); } return 0; }