Codeforces 864D(贪心)

发表于 | 分类于 | | + s

Codeforces 864D
题意：给出一个n，以及n个数，这n个数范围为1~n。 现在问最少改变几个数能使这n个数成为1~n的排列，若有多种情况，使排列的字典序最小。

第一问就是不在给的序列中的数的个数，第二问我们考虑贪心。
要使得字典序最小，那就得让前面的元素尽量小。我们把不在序列中的数全部由底至上从大到小放到一个栈里(或者小根堆)，然后我们对于重复出现的元素，一定要修改，但要留下一个。那么我们考虑留下哪一个就好了。
顺序扫一遍如果当前元素还能被替换(个数大于1), 那么如果当前栈顶比当前元素小，那就直接替换(替换时要出栈以及个数减一)；反之就要跳过这个数不修改(只能跳一次，因为是要构成排列)。这样得到的序列一定是字典序最小的。

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200000 + 5;
int vis[MAXN], cnt[MAXN], n, ai[MAXN], s[MAXN], top;
void clean() {
    ms(cnt, 0), ms(vis, 0), top = 0;
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), cnt[ai[i]]++;
    for (int i = n; i >= 1; i--) if (cnt[i] == 0) s[++top] = i;
    printf("%d\n", top);
    for (int i = 1; i <= n; i++) {
        if (cnt[ai[i]] > 1) {
            if (vis[ai[i]] || ai[i] > s[top]) cnt[ai[i]]--, ai[i] = s[top--]; else vis[ai[i]] = 1;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d ", ai[i]);
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}
------ 本文结束 ------