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行)

ARC095の他の問題 D E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告