建设银行网站怎么先无贷款呢,室内装修风格,呼伦贝尔网站建设呼伦贝尔,做网站要签合同吗题目详情点击这里
思路#xff1a;用std::stack来表示题目中说的栈#xff0c;现在关键问题就是如何找到中位数。
可以用二分答案#xff0b;树状数组的方法
由于每个元素最大不超过1e5#xff0c;因此开一个大小为1e5的树状数组来存储不超过x的数有多少个
每次push一个…题目详情点击这里
思路用std::stack来表示题目中说的栈现在关键问题就是如何找到中位数。
可以用二分答案树状数组的方法
由于每个元素最大不超过1e5因此开一个大小为1e5的树状数组来存储不超过x的数有多少个
每次push一个元素都把以它为下标的树状数组位置1pop就相当于-1
这样的话sum(x)的含义就是栈中不超过x的数有多少个。然后就可以用二分的方法把答案确定出来了。
因为中位数x肯定要满足sum(x) N/2 或者sum(x) (N1)/2
以前太菜了现在看这道题目感觉不难
代码 #include iostream
#include cstdio
#include stack
using namespace std;
const int MAX 1e5;
stackint stk;
int bitree[MAX 10];
int N;
inline int lowbit(int x)
{return x(-x);
}
void add(int pos,int x)
{while(pos MAX){bitree[pos] x;pos lowbit(pos);}
}
int sum(int pos)
{int res 0;while(pos 0){res bitree[pos];pos - lowbit(pos);}return res;
}
bool check(int x,int size)
{if(N2 0)return sum(x) size/2; else return sum(x) (size1)/2;
}
int main()
{scanf(%d,N);char ops[20];for(int i 0;i N;i){scanf(%s,ops);if(ops[1] o){if(stk.empty())puts(Invalid);else{int val stk.top();stk.pop();add(val,-1);printf(%d\n,val);}}else if(ops[1] u){int val;scanf(%d,val);stk.push(val);add(val,1);}else{if(stk.empty()){puts(Invalid);continue;}int l 0,r MAX;while(l r){int m (lr)/2;if(check(m,stk.size()))r m;elsel m1;}printf(%d\n,l);}}return 0;}
