ABC127-D_IntegerCardsをpythonで解いた（その他）

問題

• ABC127-Integer Cards

問題概要

カードが$$N$$枚あり、それぞれ整数$A_i$が書かれている。
$M$回以下の操作を行う。
カードを$B_j$枚まで選ぶ。選んだカードを$C_j$に書き換える
カードに書かれた数字の合計の最大値は？

解法

• 小さい数字のカードを書き換えるのが正解？と思いきや、書き換えるカードの枚数は決まってはいないので、その解法では間に合わない。
• カードの数字を書き換えることなく、計算する方法を考えよう。

方針

• あらかじめ$C_j$で降順ソートしてあげ、$tmp += [C_j]*B_j$ といったリストを作成
• $A + tmp$を降順ソートし、前から$N$枚の合計を計算することで、書き換えたこととなる。

例

$A = [1,2,3,4,5]$
$B,C = 2,3$
ならば、 $A + tmp = [1,2,3,4,5,3,3] = [5,4,3,3,3,2,1]$となり、$1,2$を書き換えるのが最善の操作である。

コード

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]

BC.sort(key=lambda x:-x[1])
temp = []
for i in range(M):
    temp += [BC[i][1]]*BC[i][0]
    if len(temp) > N:
        break
    
A += temp

A.sort(reverse = True)

print(sum(A[:N]))

written by 友達のtaniponyo