PAT A1057 Stack 二分写法

写法"/>

PAT A1057 Stack 二分写法

题目地址

这道题考的是优化， 肯定能拿分， 但是拿满分需要一点思考， 《算法笔记》上面用分块的方法来处理， 效率很高， 但是有点复杂， 分块也算是比较冷门的处理手段， 这道题用二分来做也可以， 而且很简单， 用空间换时间。

//我知道这道题可以分块思想来写 但是我忘了 并且我想到另外一种方法 二分法 还更简单 不过效率上面来说 比分块差很多
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main(){int n;scanf("%d",&n);vector<int> vt1, vt2;int medianIndex=0;for (int i=0; i<n; i++){char oper[20];scanf("%s", oper);if (oper[1]=='o'){//popif (vt1.empty()){printf("Invalid\n");}else {int top=vt1[vt1.size()-1];printf("%d\n",top);vt1.pop_back();auto it=find(vt2.begin(), vt2.end(), top);vt2.erase(it);}}else if (oper[1]=='u'){//pushint key;scanf("%d",&key);vt1.push_back(key);auto it=upper_bound(vt2.begin(), vt2.end(), key);vt2.insert(it, key);
//			for (auto x:vt2){
//				printf("!!!%d   ",x);
//			}}else if (oper[1]=='e'){if (vt2.empty()){printf("Invalid\n");}else {printf("%d\n",vt2[(vt2.size()-1)/2]);}}}
}

用二分来写的话， 效率差很多， 只能勉强通过，哈哈哈哈， 但是二分法容易想到， 而且代码量很少。
ps: 这道题的数据里面有大量的重复元素， 所以二分的时候用 lower_bound比用upper_bound要快不少， 但是用upper_bound也能通过。