题目粗心
现有一个栈，对其进行执行N次基本操作，该操作有三种类型，别离是Pop,Push和PeekMedian，代表了出栈，入栈和获取栈中元素的中位数，要求依照每一次输出的指令进行相应的输入
算法思路
这里最为简单的就是实时的获取栈中的中位数，应用拷贝到数组排序或者set汇合都会超时，这里借助分块的思维来实现实时获取中位数，除了应用栈st来进行入栈和出栈的基本操作之外，还须要应用block数组和table数字别离保留每一块蕴含的数字个数和每一个数字呈现的次数，第i块(i>=0)保留的数字范畴是[iblockSize,(i+1)blockSize-1]，那么求解栈的中位数的办法如下：
- 1、获取中位数的地位k=st.size()/2+st.size()%2;
- 2、应用sum示意以后累计的数字的个数
- 3、查找第k大的数字所在的块号i，第一个使得sum+block[i]>=k成立的就是第k大的数字所在的块号
- 4、查找第k大的数字在第i号块中的对应数字num，第i号块的第一个数字为iblockSize,让num=iblockSize，而后遍历num数字，只有sum+table[num]==k，就阐明以后的num就是第k大的数字。
提交后果
AC代码
#include <iostream>#include <stack>#include <string>#include <cmath>#include <cstring>using namespace std;int table[100010];stack<int> st;void push(int block[],int x){ st.push(x); ++table[x]; int blockSize = (int)sqrt(100001*1.0); ++block[x/blockSize];}int pop(int block[]){ int x = st.top(); st.pop(); --table[x]; int blockSize = (int)sqrt(100001*1.0); --block[x/blockSize]; return x;}int getMedian(const int block[]){ // 获取中位数的地位 int k = st.size()/2+st.size()%2; // 累计以后曾经呈现过的数字个数 int sum = 0; int blockSize = (int)sqrt(100001*1.0); // 查找第一个使得sum+block[i]>=k的块号i int i; for(i=0;i<blockSize;++i){ if(sum+block[i]<k){ sum += block[i]; }else{ break; } } // 第k大的数字在第i块中 int num;// 保留以后遍历的数字 int start = i*blockSize; int end = (i+1)*blockSize; for(num=start;num<end;++num){ if(sum+table[num]<k){ sum += table[num]; }else{ // 以后num就是第k大的数字 break; } } return num;}int main() { int blockSize = (int)sqrt(100001*1.0); int block[blockSize]; memset(block,0,sizeof(block)); int n; scanf("%d",&n); string str; int num; for(int i=0;i<n;++i){ cin>>str; if(str=="Pop"){ if(st.empty()){ printf("Invalid\n"); }else{ printf("%d\n",pop(block)); } }else if(str=="Push"){ cin>>num; push(block,num); }else{ if(st.empty()){ printf("Invalid\n"); }else{ printf("%d\n",getMedian(block)); } } } return 0;}