外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

C - Nyan cafe in Nyan star

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 250 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

ねこカフェの魅力度は、そのカフェで一番かわいさが低いねこで決まります。そのため、かわいさが低いねこ同士を同じカフェにまとめると、他のカフェの魅力度が下がらずに済みます。

そこで 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)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。