小球的颜色 - Problem - CGOJ

Problem M: 小球的颜色

Problem M: 小球的颜色

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 128 MiB

Submit ProblemList Solved: 0 Submit Num: 5 Statistics ShowOff!

Description

给定

lns="http://www.w3.org/1998/Math/MathML"> n

个数字

lns="http://www.w3.org/1998/Math/MathML"> a_{1}, a_{2}, \dots, a_{n}

。我们需要更改一些数字，使得最后数字种类不超过

lns="http://www.w3.org/1998/Math/MathML"> k

种，请问最少需要更改多少数字。

Input

第一行：两个整数 $lns="http://www.w3.org/1998/Math/MathML"> n$ 与 $lns="http://www.w3.org/1998/Math/MathML"> k$ ;
第二行： $lns="http://www.w3.org/1998/Math/MathML"> n$ 个整数 $lns="http://www.w3.org/1998/Math/MathML"> a_{1}, a_{2}, \dots, a_{n}$ 。

数据范围

对于 $lns="http://www.w3.org/1998/Math/MathML"> 30 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq n \leq 100$ ；
对于 $lns="http://www.w3.org/1998/Math/MathML"> 40 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq n \leq 1000$ ；
对于 $lns="http://www.w3.org/1998/Math/MathML"> 100 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq k \leq n \leq 2 \times 1 0^{5}$ 。
$lns="http://www.w3.org/1998/Math/MathML"> 1 \leq a_{i} \leq n$

Output

单个整数，表示答案。

Sample Input Copy

5 2
1 1 2 2 5

HINT

将颜色为5的小球改成2即可

Submit