Median POJ3579

投稿日：2022/09/13 更新日:2022/09/13

問題

$N$ 個の数 $X_1,X_2,...,X_N$ が与えられます。この中から２つ選びその絶対値の差 $|X_i - X_j|(1\leqq i < j \leqq N)$ を求めます。全部で ${}_NC_K$ 個あるのでその中央値を求めてください。もし、偶数個の場合は $m/2$ 番目の数を求めてください

解法

$|X_i - X_j| \geqq v$ を満たす組み合わせは何個あるかで２分探索をします。

あらかじめ数列をソートしておきます。 $i$ を固定したとき、 $X_j \geqq X_i+v$ が成り立つ $X_j$ を２分探索で求めれば個数がすぐに求まります。実装ではlower_boundを使用しています。

実装

cin、coutを使うとTLEしました。scanf、printfを使って922MSだったのでギリギリです。厳しい。。。。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        vector<int> a(n);
        for(int i = 0;i < n; ++i){
            scanf("%d", &a[i]);
        }

        sort(a.begin(), a.end());

        long long med = 1LL*n*(n-1)/4+1;

        int ng = 1e9+10, ok = 0;
        while(ng - ok > 1){
            int mid = (ok+ng)/2;

            long long count = 0;
            for(int i = 0;i < n; ++i){
                count += a.end() - lower_bound(a.begin()+i+1, a.end(), a[i]+mid);
            }

            if(count >= med){
                ok = mid;
            }else{
                ng = mid;
            }
        }

        printf("%d\n", ok);
    }
    return 0;
}