CF1195A Drinks Choosing

夏季信息学学校的老学员们还记得以前的夏令营，在晚餐时每个学生都能得到自己喜欢的饮料。或者，这个故事其实更复杂？ 现在有 $n$ 个学生住在一栋楼里，每个学生最喜欢的饮料 $a_i$ 已知。也就是说，你知道 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$（$1 \le a_i \le k$）表示第 $i$ 个学生喜欢的饮料类型。饮料类型编号为 $1$ 到 $k$。 饮料套餐的数量是无限的。每份套餐包含两份相同类型的饮料。换句话说，总共有 $k$ 种套餐，第 $j$ 种套餐包含两份第 $j$ 种饮料。每种套餐的数量都是无限的。 你知道，为了让所有学生都能恰好得到一份饮料，学生们会拿到最少数量的套餐。显然，套餐的数量恰好是 $\lceil \frac{n}{2} \rceil$，其中 $\lceil x \rceil$ 表示对 $x$ 向上取整。 在学生们拿到套餐后，他们会自行分配饮料：每个学生恰好得到一份饮料。注意，如果 $n$ 是奇数，则会剩下一份饮料没有人喝，这份饮料会被老师喝掉。 如果选择 $\lceil \frac{n}{2} \rceil$ 份套餐最优地，并且学生们最优地分配饮料，最多有多少学生能喝到自己最喜欢的饮料？

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 1000$），分别表示学生人数和饮料种类数。 接下来的 $n$ 行，每行一个整数，表示每个学生喜欢的饮料类型，第 $i$ 行的整数是 $a_i$，$1 \le a_i \le k$。

输出一个整数，表示最多有多少个学生能喝到自己喜欢的饮料。

在第一个样例中，学生们可以选择三份饮料套餐，分别是 $1$、$1$ 和 $2$（即两份类型为 $1$ 的套餐和一份类型为 $2$ 的套餐，得到的饮料份数为 $1, 1, 1, 1, 2, 2$）。这样，除了第二个学生外，其他学生都能喝到自己喜欢的饮料。 另一种可行的方案是选择 $1$、$2$ 和 $3$ 三种套餐，这样得到的饮料份数为 $1, 1, 2, 2, 3, 3$。此时，除了一个学生外，其他学生都能喝到自己喜欢的饮料。唯一喝不到喜欢饮料的学生是 $a_i = 1$ 的某个学生（即第一个、第三个或第四个）。 由 ChatGPT 4.1 翻译