[AtCoder] ABC 169 E – Count Median

2020年12月12日

問題

方針

自然数 \( 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;
}