这是第一篇在POJ的题解2333

URL:POJ

题面描述:

给出n个数，问它们两两之间差的中位数

思路:

先给这些数排序，二分答案它们的中位数，使用lower_bound计算有几个大于$x_i+mid$的，因为如果它大于$x_i+mid$，它在那个数组中的数与$x_i$的差就大于mid了

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005 
using namespace std;
long long x[N],z[N];
long long n,k,ans;
bool OK(int mi){
    long long cnt=0;
    for(int i=0;i<n;i++) cnt+=x+n-lower_bound(x+i+1,x+n,x[i]+mi);
    return cnt<=k/2;
}
int main(){
    while(~scanf("%lld",&n)){
        for(int i=0;i<n;i++) scanf("%lld",&x[i]);
        sort(x,x+n);
        k=n*(n-1)/2;
        int l=0,r=*max_element(x,x+n);
        while(r-l>1){
            int mid=l+(r-l)/2;
            if(OK(mid))r=mid;
            else l=mid;
        }
        printf("%d\n",l);
    }
    return 0;
}