题目背景
翻译自 NordicOI 2023 B 题 Ice Cream Machines。
题目描述
在你的冰淇淋店里有 n 个顾客在排队,店里一共有 m 种口味,每个人都有想买的口味,但是很不幸,店内只有 k 台机子,无法完全供应所有的口味,所以,如果下一个人要的和这台机子内原有的口味不同时,他需要清洗这台机子并更换成他喜欢的口味。
现在这 n 个人按照从 1∼n 的顺序买冰淇淋,你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子,使得清洗机子的次数最少,输出这个最少次数。
注意一台机子如果之前没人用的时候默认需要被清洗(自始至终没人用则不需要)。
输入格式
第一行三个整数 n(1≤n≤2×105),m(1≤m≤2×105) 和 k(1≤k≤2×105),分别表示一共有 n 个人,店里有 m 种口味的冰淇淋和 k 台机子。
然后 n 行,每行一个整数 ci(1≤ci≤m),表示第 i 个人喜欢吃的口味编号。
输出格式
输出清洗次数最少时所需的次数。
提示
本题采用捆绑测试。
- Subtask 1(7 points):n≤1000,m≤10,k=1。
- Subtask 2(12 points):n≤1000,m≤10,k≤2。
- Subtask 3(22 points):n≤1000,m≤10,k≤5。
- Subtask 4(11 points):n≤1000,m≤200,k≤100。
- Subtask 5(14 points):n≤2×105,m≤500,k≤100。
- Subtask 6(13 points):n≤2×105,m≤2×105,k≤100。
- Subtask 7(21 points):无特殊限制。
对于所有测试数据,1≤n≤2×105,1≤m≤2×105,1≤k≤2×105,1≤ci≤m。