POJ 3579: Median

概要

N個の配列が与えられる．この中から2つの要素を取り出し，その差を計算し別の数列とする．
新しく作った配列の中央値を探索する．ただし，この問題において偶数長(m)の配列の中央値はm/2番目に小さい値と定義する．

解法

解を仮定して二分探索．

入力された配列はソートする．（絶対値をとっていて，順番には左右されないので）
そうすることで，個数のカウントが二分探索を使って行える．

制限時間がかなり厳しい．

int N;
int x[100010];
ll M;
bool C(int mid){
    ll cnt = 0;
    for(int i = 0; i < N; ++i){
        cnt += lower_bound(x + i + 1, x + N, x[i] + mid) - (x + (i + 1));
    }
    return cnt < M;
}
int main(){
    while(~scanf("%d", &N)){
        for(int i = 0; i < N; ++i) scanf("%d", x+i);
        M = (ll)N * (N - 1) / 2;
        if(M % 2) M = M / 2 + 1;
        else      M = M / 2;

        sort(x, x+N);
        int lb = 0, ub = 1000000010;
        while(ub - lb > 1){
            int mid = (lb + ub) / 2;
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%d\n", lb);
    }
    return 0;
}