(luogu1168)中位数 发表于 2018-08-13 | 分类于 solution , 数据结构 , 树状数组 思路:值域树状数组+二分查找 将数据离散化, 用树状数组维护每个数的个数, 再用二分查找寻找当前的中位数 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int Mn(100050);inline int lb(const int& x) { return x&(-x); } //lowbitint a[Mn],b[Mn],p[Mn],c[Mn]; //a为数字,c为树状数组bool _cmp(const int& x,const int& y) //离散化时需要的排序方案{ return a[x]==a[y] ? x<y : a[x]<a[y]; }int qry(int p) //树状数组查找{ int ret(0); for(;p;p-=lb(p)) ret += c[p]; return ret;}int main() { int n; scanf("%d",&n); for(int i(1);i<=n;++i) { scanf("%d",a+i); b[i] = i; //b为离散化数组到数组的映射 } sort(b+1,b+n+1,_cmp); for(int i(1);i<=n;++i) p[b[i]] = i; //p为数组到离散化数组的映射(即b的反操作) for(int i(1);i<=n;++i) { for(int j(p[i]);j<=n;j+=lb(j)) ++c[j]; if(i%2) { int tar((i+1)/2); //查找目标 /*----二分查找----*/ int l(1),r(n); while(r-l>3) { int mid((l+r)>>1); if(qry(mid)<tar) l = mid+1; else r = mid; } int pos(l); for(;pos<=r;++pos) if(qry(pos)==tar) break; /*----------------*/ cout << a[b[pos]] << endl; } } return 0;}