Codeforces 864D - Make a Permutation! （贪心）-蒲公英云

Codeforces 864D - Make a Permutation! （贪心）

题意：给一个n，然后给出n个范围在1到n之间的数，问最少改变几个数字才能得到一个完整的从1到n的序列，然后输出这个序列并保证这个序列的字典序最小。

分析：改变个数就是1~n没有出现的数的个数。我们记录每个数出现了几次。把没有出现过的数从小到大放到队列里。一个数出现多次，就把它替换掉。同一个数出现有多个位置，则保留一个位置不变化。若这个数没有被保留过，如果小于队列里最顶端的数，这个数就被保留。如果被保留过，或小于队列里最顶端的数，那么这个位置的数改为队列里最顶端的数。这样做保证了字典序最小。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+5;
int n,m,a[N],vis[N],cnt[N];
int main() {
    while(~scanf("%d",&n)) {
        memset(vis,0,sizeof(vis));
        memset(cnt,0,sizeof(cnt));
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            cnt[a[i]]++;
        }
        queue<int>q;
        for(int i=1; i<=n; i++)
            if(cnt[i]==0)
                q.push(i);
        int ans=0;
        for(int i=1; i<=n; i++) {
            if(cnt[a[i]]>1) {
                if(vis[a[i]]==0&&a[i]<q.front()) ///没填过，且比队列最顶端的数小
                    vis[a[i]]=1;
                else {
                    ans++;
                    cnt[a[i]]--;
                    a[i]=q.front();
                    q.pop();
                }
            }
        }
        printf("%d\n",ans);
        for(int i=1; i<=n; i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}