atcoder ABC 309 C - Medicineの解答

atcoder.jp

・考え方：飲み終わるのが遅い順にソートして、累積和を取る。累積和がKを超えたら、そのindexがそのまま答えのaのindexに相当する。

n,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

ab.sort(reverse=True)
tmp=[]
t=0
#最後まで飲む順で累積和
for i in range(n):
  t+=ab[i][1]
  tmp.append(t)

#累積和がkを超えたら、そのindexのaの値+1を出力する。
for i in range(n):
  if tmp[i]>k:
    print(ab[i][0]+1)
    exit()
print(1)  #超えなかったら1日目でK以下である