日刊競プロ ABC 121 - C - Energy Drink Collector -
問題文
栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、M 本の栄養ドリンクを買い集めることにしました。栄養ドリンクが売られている店は N 軒あり、i 軒目の店では 1 本 Ai円の栄養ドリンクを Bi本まで買うことができます。最小で何円あれば M 本の栄養ドリンクを買い集めることができるでしょうか。なお、与えられる入力では、十分なお金があれば M 本の栄養ドリンクを買い集められることが保証されます。
制約
入力は全て整数である。
1≤N,M≤10**5
1≤Ai≤10**9≤10**9
1≤Bi≤10**5
B1+...+BN≥M
考えたこと
必要な数を揃えるために、まずは単価で安いものを並べる。そこから順に安いものをあるだけ買っていけば良いと考えた。
N,M = map(int,input().split())
d = []
for _ in range(N):
A,B = map(int,input().split())
d.append([A,B])
score_d= sorted(d, key=lambda x:x[0])
ans = 0
for i in score_d:
if M>i[1]:
M-=i[1]
ans+=i[0]*i[1]
elif M<=i[1]:
ans+=i[0]*M
M=0
break
print (ans)余談だが、A,Bをはじめ辞書で作成したところ、同じ単価のAがある場合にまとめられてしまう現象がおき、WAになった。連想配列等を使わない限りは２重配列を使った方が良さそうだ。