P9202

zzx0102 · 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;
}