【pythonでABC187を解説】D - Choose Me

問題概要

問題ページ

問題文

AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。
市には \(N\) 個の町があり、\(i\) 番目の町には青木派の有権者が \(A_i\) 人、高橋派の有権者が \(B_i\) 人います。他に有権者はいません。
高橋氏は、それぞれの町で演説を行うことができます。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。
一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？

制約

• 入力は全て整数
• \(1 \le N \le 2 \times 10^5\)
• \(1 \le A_i, B_i \le 10^9\)

問題の考察

問題の言い回しが少し冗長な感じがする問題で、問題を単純に言い換えると次のようになる。

このように考えると問題がかなり単純化する。

次に、「高橋氏がどの町で演説するか」を考えるが「効果の高い街から優先する」ことになり、効果が高い街とは「青木氏と高橋氏の得票の差がより縮まる（または逆転する）町」である。

各町の票数を配列に格納する際に「青木派\(\times 2 + \)高橋派」を一緒に格納（ab.append([2 * a + b, a, b])）してからsort()することで効率の良い順番で処理することができる。

後は、青木氏の票を高橋氏が上回った時点で演説した町の数を出力すれば良い。

たびすけ

票差が各町の青木派\(\times 2 + \)高橋派の分だけ縮まることが分かれば簡単な問題です！

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ab = []
    takahashi = 0
    aoki = 0
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        aoki += a
        ab.append([2 * a + b, a, b])
    ab.sort(reverse=True)
    cnt = 0
    for dif, a, b in ab:
        cnt += 1
        takahashi += a + b
        aoki -= a
        if takahashi > aoki:
            print(cnt)
            exit()


if __name__ == '__main__':
    solve()