解説
ねこカフェの魅力度は、そのカフェで一番かわいさが低いねこで決まります。そのため、かわいさが低いねこ同士を同じカフェにまとめると、他のカフェの魅力度が下がらずに済みます。
そこで C を昇順に並べ替え、前から K 匹ずつ区切って各カフェに入れます。各カフェの魅力度はそのグループの最小値です。それらの総和が答えになります。
(証明略)
キューで実装した例です。
from collections import deque
N, M, K = map(int,input().split())
C = list(map(int,input().split()))
C.sort()
d = deque(C)
ans = 0
for i in range(M):
min_ = d[0]
for _ in range(K):
d.popleft()
ans += min_
print(ans)
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。