P9199 题解
zzx0102
·
·
题解
盲猜复杂度 $O(nk)$。
考虑贪心求解。
显然，假如一段中缺少了任何一个 $<k$ 的数，则不成立。
或者 $k$ 在集合中，依旧不成立。
那么从 $1$ 到 $n$ 枚举一遍，什么时候成立了就改一次，然后接着试。
判断成不成立可以考虑用 set。先把 $0$ 到 $k-1$ 全推进去，然后把 $a_i$ 删掉。
什么时候 $a_i=k$ 了就把 $0$ 到 $k-1$ 推回去。
集合空时说明需要修改。
复杂度 $O(nk\log k)$，当且仅当所有 $a_i=k$ 时取到。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define W while
#define I inline
namespace SlowIO{
I int read() {
int x = 0, f = 1; char ch = gc();
W(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
return x * f;
}
I void Read(int &x) {x = read();}
} using namespace SlowIO;
const int N = 5010;
int n, k; int a[N], cnt[N]; set<int> st;
signed main() {
cin >> n >> k; int ans = 0;
for(int i = 1; i <= n; i++) Read(a[i]);
for(int i = 0; i < k; i++) st.insert(i); // 初始化
for(int i = 1; i <= n; i++) {
if(a[i] == k) { // = k,全部推回去
for(int i = 0; i < k; i++) st.insert(i);
continue;
}
st.erase(a[i]); // 删掉
if(st.empty()) { // 删完
ans++; // 修改一次
for(int i = 0; i < k; i++) st.insert(i); // 重新开始
}
}
cout << ans;
return 0;
}
```