题意
Description
堆栈是一种经典的后进先出的线性结构，通常有入栈(Push)和出栈(Pop)两个操作。
某人觉得这样不够好玩，就自己模拟了一个栈，并加上了取中值(GetMedia)操作。
即，返回(不取出)栈中所有元素的最中间那个元素。若最中间的元素有两个，则返回更靠前的那个。
Input
输入包括很多行(行数 $\le 10^5$)，每行都是一个操作。
如果操作命令是Push，则后面会紧跟一个空格和数字$t$ ( $0 \le t\le 10^5$ )，表示要把$t$入栈。如：Push 3。
如果操作命令是Pop，则此行它后面什么都不会出现，表示要出栈一个元素。
如果操作命令是GetMedia，则此行它后面什么都不会出现，表示要返回栈中最中间的那个数。
数据保证每个操作命令不包含空格，即不会出现操作Get Media等。
Output
符合上述3种描述的输入都是合法输入，但不一定是合法操作。例如在栈空时尝试Pop命令就是非法的。
如果是Push命令，就把它后面的整数入栈。
如果是Pop命令，就出栈一个元素并输出。
如果是GetMedia命令，就输出中间的元素。
操作过程中若出现任何非法情况，则这个操作取消并输出What are you Nong Sha Li?。
思路
比较简单的思路就是用数组进行模拟，要注意对非法情况的判断。
还有一种思路就是维护一个栈和一个vector容器
有点思维的题。在动态求中位数时，一般都是用对顶堆维护。但是对顶堆的删除操作不容易实现。
先考虑暴力的做法，是维护一个栈和一个vector容器，每次询问时都对vector进行sort，这样复杂度是O ( n 2 )
如果在插入的时候就保持vector的有序，每次查询时都二分查找该数在有序列表中的位置，时间复杂度就降到了O ( n l o g n + c )
代码
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+100; int a[maxn],idx; int main(){ string op; while(cin>>op){ if(op=="Pop"){ if(idx<=0) puts("What are you Nong Sha Li?"); else{ idx--; cout<<a[idx]<<endl; } } else if(op=="Push"){ int x;cin>>x; a[idx++]=x; } else if(op=="GetMedia") { if(idx<=0) puts("What are you Nong Sha Li?"); else{ cout<<a[(idx-1)/2]<<endl; } } else puts("What are you Nong Sha Li?"); } return 0; }
