AtCoder初心者 DailyTrainingメモ 2023/11/19

ABC229 C-問題

ポイント
Wグラムしかかけれないので、美味しいチーズから順番に使っていく（貪欲法）

229C.py

# 入力例
3 5
3 1
4 2
2 3

N,W = map(int,input().split())

リストに格納する
Cheeses = []
for _ in range(N):
    A,B = map(int,input().split())
    Cheeses.append((A, B))

# Cheeses:[(3, 1), (4, 2), (2, 3)]

# 降順にソートして美味しい順にする
Cheeses.sort(reverse = True)

# Cheeses:[(4, 2), (3, 1), (2, 3)]

ans = 0

# 美味しいチーズから使っていく
for A,B in Cheeses:
    if W >= B:  # Bグラム引いても残るので
        ans += A * B
        W -= B  # WからBグラム引く
    else:
        ans += A * W    # 残りWグラム分のチーズをかける
        break

print(ans)