单页面竞价网站,网站建设又叫什么,深圳公司网站建设哪里专业,洛卡博网站谁做的题意
给我们一个n表示操作数量 然后三种操作 push和pop 还有求中位数的操作 让我们根据操作输出正确的解
分析
用sort排序做 或者 map标记法都会超时 考虑更快的方法 如何快速找到给定一串数的中位数 可以去索引 但是需要排序 题目中告诉我们每个元素都小于1e5 那么也…题意
给我们一个n表示操作数量 然后三种操作 push和pop 还有求中位数的操作 让我们根据操作输出正确的解
分析
用sort排序做 或者 map标记法都会超时 考虑更快的方法 如何快速找到给定一串数的中位数 可以去索引 但是需要排序 题目中告诉我们每个元素都小于1e5 那么也就是说 上下界已知 那么求中位数 也就是求小于等于某个数的个数正好为所有数的一半 那么求小于等于某个数的个数 可以用树状数组去记录 然后查中位数时 在树状数组中二分小于等于的个数mid的元素的下界 树状数组可以用来统计小于等于某元素的数量
code
#includebits/stdc.h
using namespace std;
/*树状数组中记录的是小于当前元素的数量 由于树状数组符合单调性 所以可以二分这个容量的中间值
*/
char a[20];
int c[100003];
vectorints;
void add(int x,int i){while(x100000){c[x]i;xx(-x);}
}
int sum(int x){ //统计小于x的数量 int ans 0;while(x){ansc[x];x-x(-x);}return ans;
}
int find(int md){int l 0,r 100000,mid,ans;while(lr){//二分查找小于等于mid元素的数量 mid lr1;int ss sum(mid);if(ssmd)r mid-1;else l mid1;} return l;
}
int main()
{int n;scanf(%d,n);while(n--){scanf(%s,a);if(a[1]o){if(s.size()0){puts(Invalid);continue;}printf(%d\n,s[s.size()-1]);add(s[s.size()-1],-1);s.pop_back();}else if(a[1]u){int val;scanf(%d,val);add(val,1);s.push_back(val); } else{if(s.size()0){puts(Invalid);continue;}int f s.size()11;printf(%d\n,find(f));}}return 0;
}
