[AtCoder] ABC 169 E – Count Median
問題
方針
自然数 \( m \) を
\[ m = \left \lfloor \dfrac{N}{2} \right \rfloor\]
とします。
\( N \) が奇数のとき
中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順に並べた時の \( B_m \) となります。したがって、
\[ B_m – A_m + 1 \]
が答えとなります。
\( N \) が偶数のとき
中央値 \( x \) の範囲は、
\[ \dfrac{A_{m – 1} + A_{m}}{2} \leq x \leq \dfrac{B_{m – 1} + B_{m}}{2}\]
となり、\( A_{m – 1} + A_{m} \) から \( B_{m – 1} + B_{m} \) まで \( 1 \) 刻みずつ動くので、答えは、
\[B_{m – 1} + B_{m} – (A_{m – 1} + A_{m}) + 1 \]
となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; ll A[N], B[N]; for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; } sort(A, A + N); sort(B, B + N); if (N % 2 == 1) { cout << B[N / 2] - A[N / 2] + 1<< "\n"; } else { cout << B[N / 2] + B[N / 2 - 1] - (A[N / 2] + A[N / 2 - 1]) + 1 << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません