AtCoder-arc101_bMedianofMedians分析与解答

Median of Medians - AtCoder arc101_b - Virtual Judge

寻找中位数们的中位数，使用二分搜索，在数列a的最小值和最大值之间搜索，

在一列数m1,m2,m3......m_n中，如果x是他们的中位数，应该满足大于等于x的数的数目大于等于

n-[n/2]，并且x是满足该条件的最大数

比如1,2,3,4中，x=3是满足两个数（4-[4/2]）大于等于x的最大x值

比如 1,2,3,4,5中，x=3是满足三个数(5-[5/2]）大于等于x的最大x值

所以可以统计，在所有的中位数中，满足大于等于x的数的个数

如果统计给定一个区间[l,r]，快速判断这个区间的中位数是否大于等于x呢：

通过观察，将这个区间的数不降序排列后，如果区间内大于等于x的数的数目（区间中数的个数为n）大于等于(n-[n/2])，则该区间的中位数大于等于x

比如1 2 3 4，x=3，大于等于3的个数是2=4-[4/2]

比如1 2 3 4 5,x=3，大于等于3的个数是3=5-[5/2]

将一个区间中的数分成两类，大于等于x的数令其为1，否则令其为-1，则当这个区间的数的和大于等于0的时候，这个区间的中位数大于等于x

例如1 2 3 4，变为 -1 -1 1 1，和为0

这样处理后，求一个区间的和可以通过前缀和快速计算，给定区间端点l和r，如果pref[r]-pref[l-1]>=0，则这个区间的中位数大于等于x

通过移项得到 pref[r]>=pref[l-1]，（r>=l>l-1），也就是在pref数组中出现几个逆序对就有几个区间的中位数不大于等于x

因为l=1时，l-1=0，所以pref数组对于逆序对的计数要从下标0开始，统计逆序对的方法有归并排序和树状数组

复杂度 log(10^9)（二分查找）*Nlog(N)（使用树状数组）

#include<iostream> #include<cstdio> #include<climits> #include<cstring> using namespace std; #define int long long #define lowbit(x) (x&(-x)) const int maxn=2*1e5+5; int tree[maxn],a[maxn],pref[maxn]; int n; void update(int x,int d){ while(x<=maxn){ tree[x]+=d; x+=lowbit(x); } } int query(int x){ int res=0; while(x){ res+=tree[x]; x-=lowbit(x); } return res; } int satisfy(int x){ memset(tree,0,sizeof(tree)); int t=n*(n+1)/2; //总数目 int tar=t-t/2; //顺序对数目应该大于等于这个数 int cnt=0; int minpref=0; pref[0]=0; for(int i=1;i<=n;i++){ pref[i]=pref[i-1]; if(a[i]>=x){ pref[i]++; }else { pref[i]--; } minpref=min(minpref,pref[i]); } int base=-minpref+1; for(int i=0;i<=n;i++){ pref[i]+=base+1; } for(int i=n;i>=0;i--){ cnt+=query(pref[i]-1); update(pref[i],1); } if(t-cnt>=tar){ return 1; }else { return 0; } } int bin_search(int l,int r){ int ans=-1; while(l<r){ int mid=(l+r)>>1; //printf("l=%lld r=%lld mid=%lld\n",l,r,mid); if(satisfy(mid)){ //printf("%lld满足！\n",mid); ans=mid; l=mid+1; }else { r=mid; } } return ans; } signed main() { ios::sync_with_stdio(0);cin.tie(0); cin>>n; int maxa=-1,mina=INT_MAX; for(int i=1;i<=n;i++){ cin>>a[i]; maxa=max(maxa,a[i]); mina=min(mina,a[i]); } cout<<bin_search(mina,maxa+1)<<"\n"; return 0; }