1057. Stack (30)

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1057

2. 思路：

3. 源码（已AC）：

#include<iostream>#include<stack>#include<vector>#include<set>#include<functional>//使用仿函数greater<int>using namespace std;int main(void){	//freopen("in.txt", "r", stdin);	int N;	char s[15];	stack<int> st;	multiset<int> small;//小根堆	multiset<int, greater<int> > big;//大根堆	scanf("%d", &N);	for (int i = 0; i < N; i++)	{		scanf("%s", s);		if (s[1] == 'o')		{			if (st.empty())				printf("Invalid/n");			else			{				int num = st.top();				printf("%d/n", num);				if (num > *big.begin())					small.erase(small.find(num));//删除不能用值做参数，会删除多个。				else					big.erase(big.find(num));				st.pop();			}		}		else if (s[1] == 'u')		{			int num;			scanf("%d", &num);			st.push(num);			if (!big.empty() && num > *big.begin())				small.insert(num);			else				big.insert(num);		}		else		{			if (big.empty())				printf("Invalid/n");			else				printf("%d/n", *big.begin());		}		if (small.size() > big.size())//对两个堆进行维护，确保符合要求。		{			big.insert(*small.begin());			small.erase(small.begin());		}		else if (big.size() > small.size() + 1)		{			small.insert(*big.begin());			big.erase(big.begin());		}	}	return 0;}