ABC187 解説（D - Choose Me）

D - Choose Me

D - Choose Me

• 貪欲法を用いる

何もしなければ，青木君はすべての票を，高橋君は0票となる．もし，町で高橋君が演説をすれば，青木君の票が票減り，高橋君の票が票増える．注意点は「 青木君の総得票数」<「高橋君の総得票数」となるときの演説回数なので，高橋君が得票すること以外にも青木君の票を減らすことも重要である．

どの町で演説するのがよいか

ある町の青木派が人，高橋派が人いたとする．この町で演説する場合としない場合の青木君と高橋君の得票数の差を調べる．

	演説なし	演説あり
青木君
高橋君

となることから，演説ありと，演説なしのときの得票数の差の差はである．つまり，この町で演説した場合票だけ青木君の得票数と，高橋君の得票数の差が縮まることがわかる．したがって，この値が大きい町から順番に演説をすればよい．したがって，次のような実装になる．

N = int(input())
AB = []
for i in range(N):
  a,b = map(int,input().split())
  AB.append([2*a+b,a,b])

AB.sort(reverse = True)
sumA = 0
sumB = 0
for x in AB:
  sumA += x[1]

ans = 0
if sumA < sumB:
  print(ans)
  exit()
for i in range(N):
  sumA -= AB[i][1]
  sumB += AB[i][1] + AB[i][2]
  ans += 1
  if sumA < sumB:
    print(ans)
    exit()