CodeForces 864D Make a Permutation! 【贪心】【模拟】

发表于 | 更新于 | 分类于

题目大意：

给出n个数，每次可以花费1单位体力来将其中的任意一个数改变为任意一个数。现在他想要将这n个数经过若干次变换，使之包含1-n的所有数字。问他改变完成后花费的最小体力，并输出改变后的序列。如果存在多组解，输出这全排列中字典序最小的哪种方案。

解题思路：

既然花费体力最小，那当然要优先考虑将出现过多次的数字替换为未出现的数字了。然后就是稍微困难点的部分了——字典序最小。
我们考虑一下替换过程中可能会出现的情况可以发现，当一个数要被替换时，如果替换为的数小于这个数，那就取最靠前的数字来进行替换，否则就取靠后的来替换。（如11123 -> 14523, 23334 -> 21354）
接下来的实现，先找一个数组记录这个序列，再找一个来记录每个数字出现的次数。因为最终替换为的是没有出现过的数字，所以还要记录下哪些数字没有出现过，这里可以用set也可以用priority_queue。最后遍历一遍原序列，开始进行替换（即出现次数大于一次的要被没出现过的替换掉）。因为还要比较大小关系，如果被替换的数>要替换的数，直接替换就好了；否则标记下这个数，这里没有替换，以后再遇到不管怎样都要替换掉（再加个vis数组标记一下就好了）。

Mycode：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 200005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, tot;
bool vis[MAX];
int a[MAX], b[MAX];
priority_queue <int, vector<int>, greater<int> > Q;
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        ++b[a[i]];
    }

    for(int i = 1; i <= n; ++i) if(!b[i])   Q.push(i);

    for(int i = 1; i <= n; ++i)
    {
        if(Q.empty())   break;
        if(b[a[i]] > 1)
        {
            if(Q.top() < a[i] || vis[a[i]])
            {
                ++tot;
                --b[a[i]];
                a[i] = Q.top();
                Q.pop();
            }
            else
                vis[a[i]] = true;
        }
    }

    printf("%d\n", tot);
    for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
    return 0;
}
Donate comment here
0%