1207: 删除(noip模拟题)

内存限制:256 MB 时间限制:10.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:44 通过:5

题目描述

现在,我的手上有 n 个数字,分别是 a 1 ,a 2 ,a 3 ,...,a n 。我现在需要删除其中的 k 个数字。当然我不希望随随便便删除,我希望删除 k数字之后,剩下的 n − k 个数中有最多的不同的数。

输入格式

第一行两个正整数 n 和 k,含义如题目描述。
接下来一行,有 n 个非负整数,分别是 a 1 到 a n 。

输出格式

一共一行,一个整数 ans,表示删除了 k 个数字后最多的不同的数的个数。

输入样例 复制

4 1
1 3 1 2

输出样例 复制

3

数据范围与提示

如果删去第一个 1:
在[3,1,2]中有 3 个不同的数
如果删去 3:
在[1,1,2]中有 2 个不同的数
如果删去第二个 1:
在[1,3,2]中有 3 个不同的数
2
如果删去 2:
在[1,3,1]中有 2个不同的数


对于 30% 的数据,n ≤ 10,a i ≤ 10。
对于 60% 的数据,n ≤ 100,a i ≤ 100。
对于 80% 的数据,n ≤ 10 5 ,a i ≤ 10 5 。
对于 100% 的数据,n ≤ 10 5 ,a i ≤ 10 9 。

分类标签