P11931 [CrCPC 2024] AI 的末日

liaoxingrui · 2025-03-21 16:57:45 · 题解

Content

有 k 堆总共 n 件衣服和 1 个笔记本（放在任意一堆衣服上），每件衣服将在第 i 个时刻放在 a_i 这个位置，要求笔记本上面不能有衣服，问最少要移动多少次笔记本？（笔记本最开始在的位置由你决定）

Solution

我们可以发现笔记本在越后面才需要换，则越好，那么我们就可以用一个 set 将第 i 时刻的衣服所放在的位置存起来（因为 set 有去重），若判断到所有的位置都以出现，则将笔记本换到最后一个位置，再将 set 清空，并将答案加一，重复操作即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,x,ans;
set<int> s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    while(n--){
        cin>>x;
        s.insert(x);
        if(s.size()==k){
            s.clear();
            s.insert(x);
            ans++;
        }
    }
    cout<<ans;
    return 0;
}