POJ 3579 Median(二分答案+Two pointers)

【题目链接】 http://poj.org/problem?id=3579

【题目大意】

  给出一个数列,求两两差值绝对值的中位数。

【题解】

  因为如果直接计算中位数的话,数量过于庞大,难以有效计算,
  所以考虑二分答案,对于假定的数据,判断是否能成为中位数  
  此外还要使得答案尽可能小,因为最小的满足是中位数的答案,才会是原差值数列中出现过的数
  对于判定是不是差值的中位数的过程,我们用尺取法实现。
  对于差值类的题目,还应注意考虑边界,即数列只有一位数的情况。

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[100010];
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=a[n],m=n*(n-1)/4+((n*(n-1)/2)&1),ans=0;
if(n==1){puts("0");continue;}
int Ans=0;
while(l<=r){
int mid=(l+r)>>1,pre=1,ans=0;
for(int i=2;i<=n;i++){
while(a[i]-a[pre]>mid)pre++;
ans+=i-pre;
}if(ans>=m)r=mid-1,Ans=mid;
else l=mid+1;
}printf("%d\n",Ans);
}return 0;
}
上一篇:POJ 3061 Subsequence【二分答案】||【尺取法】


下一篇:BZOJ 2440 中山市选2011 全然平方数 二分答案+容斥原理+莫比乌斯反演