[C++] PAT 1057 Stack (30分)

Sample Input:

17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop

Sample Output:

Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid

题解：

该题采用了分块思想

#include <iostream> #include <stack> #include <vector> #include <string> #include <cstring> using namespace std; const int MAXN = 100010; const int BLOCKS = 316;//每块中数的个数 int table[MAXN]; int block[317];//317 是块数 stack<int> st; int main(){ int n; cin >> n; char cmd[20]; for(int i=0;i<n;i++){ scanf("%s",cmd); if(strcmp(cmd,"Pop") == 0){ if(!st.empty()){ int num = st.top(); st.pop(); cout << num << endl; int temp_block = num / BLOCKS; block[temp_block]--; table[num]--; } else{ cout << "Invalid" << endl; } } else if(strcmp(cmd,"PeekMedian") == 0){ if(!st.empty()){ int k = st.size(); if(k % 2 == 0){ k = k / 2; } else{ k = (k + 1) / 2; } int s = 0; int idx = 0;//块号 while(s + block[idx] < k){ s += block[idx++]; } int num = idx * BLOCKS; //BLOCKS是每个块最大容量 while(s + table[num] < k){ s += table[num++]; } cout << num << endl; } else{ cout << "Invalid" << endl; } } else{ int num; scanf("%d",&num); int temp_block = num / BLOCKS; block[temp_block]++; table[num]++; st.push(num); } } system("pause"); return 0; }