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; }