1057. Stack (30)

2019-11-10 20:12:57

字体：大中小

来源：转载

供稿：网友

http://blog.csdn.net/x_iya/article/details/8943264 使用树状数组，上面是树状数组的介绍有一个很大的坑是用cout的时候超时，改成PRintf就ok了，做题感觉输入输出还是用printf和scanf最快，最稳

#include<iostream>#include<string>#include<vector>#include<algorithm>#pragma warning(disable:4996)using namespace std;int c[100001] = {0};int lowbit(int n){ return n&(-n);}int GetSum(int index){ int sum=0; while (index != 0) { sum += c[index]; index -= lowbit(index); } return sum;}void Add(int value, int index){ while (index < 100000) { c[index] += value; index += lowbit(index); }}int Getmid(int size){ int index = (1 + size) / 2; int low = 1, high = 100000,mid; while (low < high) { mid = (low + high) / 2; if (GetSum(mid) < index) low = mid + 1; else high = mid; } return low;}int main(){ vector<int> sort_vec; std::ios::sync_with_stdio(false);// cout << unitbuf;// freopen("0.txt", "w", stdout); vector<int> vec; int N; cin >> N; for (int t = 0;t < N;t++) { string str; cin >> str; switch (str[1]) { case 'o': { if (vec.empty()) printf("Invalid/n" ); else { int temp = vec.back(); printf("%d/n", temp); Add(-1, temp); vec.pop_back(); } } break; case 'e': { if (vec.empty()) printf("Invalid/n"); else printf("%d/n", Getmid(vec.size())); } break; case 'u': { int x; cin >> x; vec.push_back(x); Add(1, x); } break; } }}

上一篇：RMQ算法

下一篇：历届试题核桃的数量