{"problem":{"name":"[NordicOI 2023] Ice Cream Machines","description":{"content":"在你的冰淇淋店里有 $n$ 个顾客在排队，店里一共有 $m$ 种口味，每个人都有想买的口味，但是很不幸，店内只有 $k$ 台机子，无法完全供应所有的口味，所以，如果下一个人要的和这台机子内原有的口味不同时，他需要清洗这台机子并更换成他喜欢的口味。 现在这 $n$ 个人按照从 $1 \\sim n$ 的顺序买冰淇淋，你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子，使得清洗机子的次数最少，输出这","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10647"},"statements":[{"statement_type":"Markdown","content":"在你的冰淇淋店里有 $n$ 个顾客在排队，店里一共有 $m$ 种口味，每个人都有想买的口味，但是很不幸，店内只有 $k$ 台机子，无法完全供应所有的口味，所以，如果下一个人要的和这台机子内原有的口味不同时，他需要清洗这台机子并更换成他喜欢的口味。\n\n现在这 $n$ 个人按照从 $1 \\sim n$ 的顺序买冰淇淋，你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子，使得清洗机子的次数最少，输出这个最少次数。\n\n注意一台机子如果之前没人用的时候默认需要被清洗（自始至终没人用则不需要）。\n\n## Input\n\n第一行三个整数 $n (1 \\leq n \\leq 2 \\times 10^5)$，$m (1 \\leq m \\leq 2 \\times 10^5)$ 和 $k (1 \\leq k \\leq 2 \\times 10^5)$，分别表示一共有 $n$ 个人，店里有 $m$ 种口味的冰淇淋和 $k$ 台机子。\n\n然后 $n$ 行，每行一个整数 $c_i (1 \\leq c_i \\leq m)$，表示第 $i$ 个人喜欢吃的口味编号。\n\n## Output\n\n输出清洗次数最少时所需的次数。\n\n[samples]\n\n## Background\n\n翻译自 [NordicOI 2023 B 题](https://noi23.kattis.com/contests/noi23/problems/icecreammachines) Ice Cream Machines。\n\n## Note\n\n**本题采用捆绑测试**。\n\n- Subtask 1（7 points）：$n \\le 1000$，$m \\leq 10$，$k = 1$。\n- Subtask 2（12 points）：$n \\le 1000$，$m \\leq 10$，$k \\leq 2$。\n- Subtask 3（22 points）：$n \\leq 1000$，$m \\leq 10$，$k \\leq 5$。\n- Subtask 4（11 points）：$n \\leq 1000$，$m \\leq 200$，$k \\leq 100$。\n- Subtask 5（14 points）：$n \\leq 2 \\times 10^5$，$m \\leq 500$，$k \\leq 100$。\n- Subtask 6（13 points）：$n \\leq 2 \\times 10^5$，$m \\leq 2 \\times 10^5$，$k \\leq 100$。\n- Subtask 7（21 points）：无特殊限制。\n\n对于所有测试数据，$1 \\le n \\le 2\\times 10^5$，$1 \\leq m \\leq 2 \\times 10^5$，$1 \\leq k \\leq 2 \\times 10^5$，$1 \\leq c_i \\leq m$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10647","tags":["贪心","堆","2023","NordicOI（北欧）"],"sample_group":[["8 3 1\n2\n3\n3\n1\n2\n1\n1\n3","6"],["8 3 2\n2\n3\n3\n1\n2\n1\n1\n3","4"]],"created_at":"2026-03-03 11:09:25"}}