堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。
输入格式：
输入的第一行是正整数 N（≤105）。随后 N 行，每行给出一句指令，为以下 3 种之一：
1. Push key 2. Pop 3. PeekMedian
其中 key 是不超过 105 的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。
输出格式：
对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。
输入样例：
1. 17 2. Pop 3. PeekMedian 4. Push 3 5. PeekMedian 6. Push 2 7. PeekMedian 8. Push 1 9. PeekMedian 10. Pop 11. Pop 12. Push 5 13. Push 4 14. PeekMedian 15. Pop 16. Pop 17. Pop 18. Pop
输出样例：
Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid
思路： Pop的规则是先进后出，只需要用一个数组存储，然后每次弹出最后一个数就行，PeekMedian需要取到中间值，所以需要一个排序好的序列，所以这题需要开两个数组，lower_bound(b.begin(),b.end(),x)是返回第一个大于等于x的地址
#include<bits/stdc++.h> using namespace std; int n,x; string s; vector<int>a,b; int main() { cin>>n; while(n--) { cin>>s; if(s=="Push") { cin>>x; a.push_back(x); auto it=lower_bound(b.begin(),b.end(),x); b.insert(it,x); } else if(s=="Pop") { if(a.size()==0) cout<<"Invalid\n"; else { auto it=lower_bound(b.begin(),b.end(),a[a.size()-1]);//查找需要删除的地址 b.erase(it); cout<<a[a.size()-1]<<endl; a.pop_back(); } } else { if(b.size()==0) cout<<"Invalid\n"; else { if(b.size()&1) cout<<b[b.size()>>1]<<endl;//数组下标从零开始的 else cout<<b[b.size()-1>>1]<<endl; } } } return 0; }
