PKU3579 Median

問題URL: 3579 -- Median

問題文:

n個の1次元座標が与えられるので、それで作れるnC2通りのペアの距離リストを作って、それらの中央値を求めろという問題。奇数の場合はそのまま中央値で、偶数の場合はn/2番目のものを求める。

感想: ちょっと悩んだ。こういう問題は好きです。この問題について誰か書いてる日本人いないかなと思ったらtozanが居た。

解法:

• 中央値⇔距離がその値以下のものが ceil(nC2/2) 以上個ある値 (重複とか含めるとアレだが大体それくらい)
• 中央値を二分探索で決めうちしてやる。
• ある値以下のペアの個数の数え上げは、尺取法O(n)をするかlower_bound()関数を用いるO(nlogn)する。

ソース:

TLEしたら尺取法にしようとしていたんだけれど、通ってしまった。

(1回目TLEしたがそれはcinが原因だった。)

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
int in() {
    int x = 0, c;
    for (; (uint)((c = getchar()) - '0') >= 10; ) { if (c == '-') return -in(); if (!~c) throw ~0; }
    do { x = (x << 3) + (x << 1) + (c - '0'); } while ((uint)((c = getchar()) - '0') < 10);
    return x;
}

int n,v[100000];

long long solve(int M){
	long long ans = 0;
	for(int i = 0 ; i < n ; i++)
		ans += i - (lower_bound(v,v+n,v[i]-M)-v);
	return ans;
}

int main(){
	while(~scanf("%d",&n)){
		for(int i = 0 ; i < n ; i++) v[i] = in();
		sort(v,v+n);
		long long L = ( (long long)n * (n-1) / 2 + 1)/ 2;
		
		int l = 0 , r = v[n-1] - v[0];
		for(;l!=r;){
			int m = (l+r) / 2 ;
			if( solve(m) >= L) r = m;
			else l = m+1;
		}
		printf("%d\n",l);
	}
}