Codeforces 864D(贪心)

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

------ 本文结束 ------