CF2057B Gorilla and the Exam

# Gorilla and the Exam 由于“T世代”高年级学生的教师短缺，决定由一只巨大的雄性猩猩来为学生们进行考试。然而，这并不是那么简单；为了证明其能力，它需要解决以下问题。 给定一个数组 $ b $ ，我们定义函数 $ f(b) $ 为将数组 $ b $ 变为空所需的最小操作次数： - 选择两个整数 $ l $ 和 $ r $ ，满足 $ l \le r $ ，并令 $ x $ 为数组 $ b_l, b_{l+1}, \ldots, b_r $ 中的最小值； - 然后，删除所有满足 $ l \le i \le r $ 且 $ b_i = x $ 的元素，删除后的元素将被移除，剩余元素的索引重新编号。 现在给定一个长度为 $ n $ 的数组 $ a $ 和一个整数 $ k $ 。你可以至多进行 $ k $ 次修改操作，每次可以选择数组中的任意索引 $ i $ （$ 1 \le i \le n $）和任意整数 $ p $ ，将 $ a_i $ 替换为 $ p $ 。 帮助猩猩求出经过至多 $ k $ 次替换操作后，数组 $ a $ 的 $ f(a) $ 可以达到的最小值。

- 第一行是一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 - 接下来是 $ t $ 组测试数据。 - 每组数据的第一行包含两个整数 $ n $ 和 $ k $ （$ 1 \le n \le 10^5 $，$ 0 \le k \le n $）——数组的长度和最多允许的替换次数。 - 每组数据的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ——数组 $ a $ ，其中 $ 1 \le a_i \le 10^9 $ 。 保证所有测试数据中所有数组长度的总和不超过 $ 10^5 $。

对于每组测试数据，输出一个整数——通过至多 $ k $ 次替换操作后，数组 $ a $ 的 $ f(a) $ 可以达到的最小值。

- 在第一个测试数据中，数组 $ [48843] $ 只包含一个元素，因此 $ f([48843]) = 1 $，只需一次操作即可删除该元素。 - 在第二个测试数据中，你可以将数组 $ [2, 3, 2] $ 中的第二个元素修改为 $ 2 $ ，使得数组变为 $ [2, 2, 2] $ ，此时 $ f([2, 2, 2]) = 1 $ ，因为可以选择整个数组，最小值为 $ 2 $，然后一次删除所有的 $ 2 $ 元素。