わかさぎのブログ

プログラミング、Atcoderの勉強とか

AtCoder Beginner Contest 081 C - Not so Diverse

N,K=map(int,input().split())
a=list(map(int,input().split()))

buk=[0 for i in range(1,200001)]
for i in a: buk[i]+=1

count=0
for i in buk:
    if i!=0:
        count+=1

buk=[i for i in buk if i>0]

delete=count-K
if delete<=0:
    print(0)

else:
    div=sorted(buk)
    div=div[:delete]
    suma=sum(div)
    print(suma)

考え方

バケットを利用する。
buk[i]:=数字iがbuk[i]個ある。
はじめはbuk[i]を0で初期化して、anの情報を突っ込む。
そうして0でないものの個数をカウントしてそれが数字の種類。
Kを上回っている分だけ種類を減らせばいいから、個数の少ない文字を消せばいい。
buk[i]から0を除外して小さい順にソートしてできた数列を使って、Kを上回っている分だけの項の和を取ればよい。