75

· · 个人记录

题目描述

在古老而辉煌的王朝时期，王朝上下沉浸在深厚的文化底蕴之中。彼时，礼部尚书肩负着统管全国众多学府的重任。全国共有 N座学府（编号为1至N），每座学府都有着其独特的学术氛围，尊崇研习的学术流派种类以数字 ai表示。如今，圣上高瞻远瞩，为了整合学术思想、强化文化交流与统治，特责令礼部尚书偕同诸位才高八斗的鸿儒学士，通过巧妙地变更部分学府所尊崇的学术流派，使这些学府的学术流派总数严格不超过K种。面对圣上的旨意，礼部尚书深感责任重大，他需在诸位鸿儒学士们的全力协助下制定出最为妥善的策略。那么，在这种情形之下，最少需要改变几家学府的学术流派呢？ 输入格式

第一行读入两个正整数N,K。

第二行包含 N个正整数，表示每个学府的学术流派编号。 输出格式

一个整数，表示最少要改变的学府数量。

输入数据 1

5 2 1 1 2 2 5

输出数据 1

1

【样例1解释】

当前的所有学术流派共有3种，要限制在不超过2种时，需要修改一座学府。

输入数据 2

6 1 1 1 1 2 2 6

输出数据 2

3

【样例 2解释】

当前的所有学术流派共有3种，要限制在不超过1种时，需要修改3座学府。

输入数据 3

10 3 5 1 3 2 4 1 1 2 3 4

输出数据 3

3

【样例 3解释】

当前的所有学术流派共有3种，要限制在不超过3种时，需要修改3座学府。
流派为5的学府1座,流派为4的学府2座

数据范围

对于30的数据:1≤n≤100。

对于 40%的数据1≤n≤1000。

对于 100%的数据，1≤k≤n≤2×10的5次方,1≤ai≤n。