PAT A1057 分块思想

使用的就是分块思想，之前写过总结，所以不再赘述；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<stack>#include<cstring>using namespace std;const int maxn=100010;const int sqrN=316;stack<int>st;int block[sqrN];int table[maxn];void peekMedian(int K){ int sum=0; int idx=0; while(sum+block[idx]<K){ sum+=block[idx++]; } int num=idx*sqrN; while(sum+table[num]<K){ sum+=table[num++]; } printf("%d\n",num);}void push(int x){ st.push(x); block[x/sqrN]++; table[x]++;}void pop(){ int x=st.top(); st.pop(); block[x/sqrN]–; table[x]–; printf("%d\n",x);}int main(){ int x,query; memset(block,0,sizeof(block)); memset(table,0,sizeof(table)); char cmd[20]; scanf("%d",&query); for(int i=0;i<query;i++){ scanf("%s",cmd); if(strcmp(cmd,“Push”)==0){ scanf("%d",&x); push(x); }else if(strcmp(cmd,“Pop”)==0){ if(st.empty()==true){ printf(“Invalid\n”); }else{ pop(); } }else{ if(st.empty()==true){ printf(“Invalid\n”); }else{ int K=st.size(); if(K%2==1) K=(K+1)/2; else K=K/2; peekMedian(K); } } } system(“pause”); return 0;}