ABC127 D - Integer Cards

問題原文

atcoder.jp

問題要旨

整数列 とクエリが 個与えられる。各クエリでは、 個まで 値を にできる。 （0個の操作も許される）
最適に操作を行って、クエリを全て見た後の の総和を最大化せよ。

• 入力は全て整数。
• 
• 
• 

解法

• 小さいものを大きいものに置き換えていきたい気持ちになります。
• ある を２回以上置き換え得るのが無駄であることはわかります。（最後に狙いの数字に置き換えたらその前のことは無意味なので）
• すると、書き換えは高々 回であることがわかります。
• すると、「クエリは が大きい方から、 は が小さい方から」見ていくのが良いことがわかります。
• 実装においては、 を whileでなめるために、今見ているindexを持つ変数を用意するとやりやすいです。

実装

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

query = []
for i in range(M):
    b, c = map(int, input().split())
    query.append([b, c])
query.sort(key=lambda q: q[1], reverse=True)

i = 0
for b, c in query:
    while (i < N) and (b > 0):
        if A[i] < c:
            A[i] = c
            b -= 1
        i += 1

print(sum(A))

感想

こういうのすきです。
２回以上操作するのが無駄かもしれないというのは常に意識していきたいです。