poj3579 Median

标题:100000個の大きさ10000000の数をあげて、彼らの任意の組み合わせの差の絶対値の結果は組み合わせの数C(n,2)個があって、この結果の大きい配列はきっと保存できません.これらの差の絶対値の数の中で中位数は?考え方:K番目の数は、もちろん2点です.主に判断関数です.毎回xに対して、直接2分元のシーケンスの中で現在の数に対して何個がこの範囲の数より大きいかを分けて、和を求めると、このxが差の中で何個がそれに等しい数より大きいかを知ることができるので、sumがこの差のシーケンスの中で中位数より大きい後の数であれば、このxが少なくとも満足しているか、あるいはもっと大きいxがあれば、逆にxは大きくなります.

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100000+10],n,m;
bool check(int x)
{
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=n-(lower_bound(a,a+n,a[i]+x)-a);
    }
    return sum>(n*(n-1)/2-m);//       
}

int main()
{
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        int l=0,r=a[n-1]-a[0];
        m=((n-1)*n/2+1)/2;//      
        while(l<=r){
           int mid=(l+r)/2;
           if(check(mid)) l=mid+1;
           else r=mid-1;
        }
        printf("%d
",l-1);
    }
}