ARC095 C : Many Medians(300)
作成日：2018.09.09
最終更新日：2018.09.09
問題概要
$N$個の整数$X_1,X_2,...,X_N$が与えられる。
各$i$について、これらの整数から$X_i$を除いたものの中央値を求めよ。
制約
$1 \leq N \leq 2 \times 10^5$
$N$は偶数
$1 \leq X_i \leq 10^9$
考え方
$N$は偶数であるから、各$i$においての答えは$X_i$以外で$N/2$番目に小さい整数$a_i$である。
$X_i$を含めて考えると、$X_i \geq a_i$であれば$a_i$は$N/2$番目に小さい整数であり、そうでなければ$(N/2+1)$番目に小さい整数である。
逆に考えると、$X_i$が全体で$(N/2+1)$番目に小さい整数未満であれば全体で$(N/2+1)$番目に小さい整数、そうでなければ全体で$N/2$番目に小さい整数が答えであることが分かる。
ソースコード
マクロ等はこちら
const int MC = 2e5 + 3;
int N;
int X[MC],a[MC];
int main(){
cin >> N;
repp(i,0,N){
cin >> X[i];
a[i] = X[i];
}
sort(a,a+N);
repp(i,0,N) cout << (a[N/2] > X[i] ? a[N/2] : a[N/2-1]) << endl;
return 0;
}解法まとめ
$X_i$が$X$のうち$(N/2+1)$番目に小さい整数未満なら$(N/2+1)$番目に小さい整数、そうでないならば$N/2$番目に小さい整数が答えである。(11,12行)