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

淩亂°似流年 2021-10-13 14:58 211阅读 0赞

## 题意：给一个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;
    }