題意：給你一個長度為n的數(shù)組，每個元素都在1~n之間，要你改變最少的元素，使得它變成一個1~n的排列。在保證改動最少的基礎(chǔ)上，要求字典序最小。

預(yù)處理cnt數(shù)組，cnt[i]代表i在原序列中出現(xiàn)的次數(shù)。b數(shù)組，代表沒有出現(xiàn)過的數(shù)是哪些。b數(shù)組的長度就是答案。

b數(shù)組是從小到大排好的，然后for循環(huán)b數(shù)組，同時用一個指針p指著a數(shù)組的當(dāng)前位置，最開始指向開頭，如果cnt[a[p]]==1，就向后跳，否則再看 是否b[i]<a[p]或者a[p]這個數(shù)是否已經(jīng)出現(xiàn)過了(用個hav數(shù)組表示a[p]是否已經(jīng)再前面出現(xiàn)過了)。只要滿足這兩個條件之一，就可以讓cnt[a[p]]--，然后把a(bǔ)[p]修改為b[i]。如此一定能保證字典序最小。

#include<cstdio> using namespace std; int n,a[200005],cnt[200005]; bool hav[200005]; int b[200005],e; int main(){ // freopen("d.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);++cnt[a[i]];}for(int i=1;i<=n;++i){if(!cnt[i]){b[++e]=i;}}int p=1;for(int i=1;i<=e;++i){while(cnt[a[p]]==1 || (!hav[a[p]] && b[i]>a[p])){hav[a[p]]=1;++p;}--cnt[a[p]];a[p]=b[i];}printf("%d\n",e);for(int i=1;i<n;++i){printf("%d ",a[i]);}printf("%d\n",a[n]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/autsky-jadek/p/7596253.html

總結(jié)

以上是生活随笔為你收集整理的【贪心】Codeforces Round #436 (Div. 2) D. Make a Permutation!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。