Edit

【pythonでABC169を解説】E - Count Median

問題概要

問題ページ

E - Count Median
E - Count Median

問題ページへ移動する

問題文

\(N\) 個の整数 \(X_1, X_2, \cdots, X_N\) があり、\(A_i \leq X_i \leq B_i\) であることがわかっています。
\(X_1, X_2, \cdots, X_N\) の中央値として考えられる値はいくつあるか求めてください。

注記

\(X_1, X_2, \cdots, X_N\) の中央値は次のように定義されます。\(X_1, X_2, \cdots, X_N\) を昇順に並び替えたものを \(x_1, x_2, \cdots, x_N\) とします。

  • \(N\) が奇数のとき、中央値は \(x_{(N+1)/2}\)
  • \(N\) が偶数のとき、中央値は \((x_{N/2} + x_{N/2+1}) / 2\)

制約

  • \(2 \leq N \leq 2 \times 10^5\)
  • \(1 \leq A_i \leq B_i \leq 10^9\)
  • 入力はすべて整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    al, bl = [], []
    for _ in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        al.append(a)
        bl.append(b)
    al.sort()
    bl.sort()
    if n % 2 == 0:
        s = (al[n // 2 - 1] + al[n // 2]) / 2
        e = (bl[n // 2 - 1] + bl[n // 2]) / 2
        print(int(e * 2 - s * 2 + 1))
    else:
        s = al[n // 2]
        e = bl[n // 2] print(e - s + 1) if __name__ == '__main__': solve()

-Edit
-