自动搬运

查看原文

来自洛谷，原作者为

	zzx0102 原 sto_5k_orz || AFO on 2023.10.21

搬运于2025-08-24 22:46:17，当前版本为作者最后更新于2023-04-05 20:17:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

部分说明转载自 P9199 题解。

考虑贪心求解。

显然，假如一段中缺少了任何一个 $<k$ 的数，则不成立。

或者 $k$ 在集合中，依旧不成立。

判断成不成立可以考虑用 set。

上一篇题解是先推满然后删除的，空了说明需要修改。

可是这题 $k\leq 10^9$。

所以我们应该先清空，再推进去，凑够 $k$ 个数再修改。

每次修改改成 $k$ 就可以了，因为只要让 $k$ 在集合中就肯定不成立。

还有就是不要把 $>k$ 的数推进 set。

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define W while
#define I inline
#define int long long
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();}
    I void write(int x) {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc(x % 10 + '0');
    }
    I void Write(int x) {write(x); pc(' ');}
} using namespace SlowIO;
const int N = 1000010;
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 = 1; i <= n; i++) {
		if(a[i] == k) {
			st.clear();
			continue;
		}
		if(a[i] < k) st.insert(a[i]);
		if(st.size() == k) {
			ans++; a[i] = k;
			st.clear();
		}
	}
	cout << ans << endl;
	for(int i = 1; i <= n; i++) Write(a[i]);
	return 0;
}