masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

ABC187 解説(D - Choose Me)

D - Choose Me

D - Choose Me

  • 貪欲法を用いる

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

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

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

演説なし 演説あり
青木君 a  0
高橋君 0 a+b

となることから,演説ありと,演説なしのときの得票数の差の差 (a+b) - 0 )- (0-a) = 2a+bである.つまり,この町で演説した場合2a+b票だけ青木君の得票数と,高橋君の得票数の差が縮まることがわかる.したがって,この値が大きい町から順番に演説をすればよい.したがって,次のような実装になる.

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()