【ABC187 D】「Choose Me」を解く【Python3】

コンテスト一覧へ

 

AtCoder 市で市長選挙で、高橋氏が青木氏より多く票をとるために、最小でいくつの町で演説をすればいいのか、求める問題です。

提出
n = int(input())
sa = []
am = 0

for i in range(n):
    a, b = map(int, input().split())
    am += a
    sa.append(2*a+b)

li = sorted(sa, reverse=True)
ans = 0

for i in range(n):
    am -= li[i]
    ans += 1
    if am < 0:
        break

print(ans)
  • 高橋氏が演説:全員が高橋氏に投票(青木派+高橋派)
  • 高橋氏が演説しない:青木派は青木氏に投票。高橋派は投票に行かない

ということで、「すべての町で演説しない場合」の青木派の票を求め、そこから、演説をした町の票数を引いて求めます。

演説をした町は、青木氏の票が減り(-A)、高橋氏の票が増える(A+B)ので、青木氏と高橋氏の票数の差は「2A+B」だけ縮まります。

プログラムでは、各町の「2*a+b」を大きい順にソートし、「すべての町で演説しない場合」の青木派の票amから順に引いています。

「ans」で引いた回数をカウントしています。

amが0未満で、両者の差が逆転したことになるので、ここでループを終了し、「ans」を出力します。

【ABC187】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。