題目鏈接：點擊查看

題目大意：給出一個數(shù)組 a ，要求構(gòu)造一個數(shù)組 b ，使得 a[ i ] = MEX{ b[ 1 ] , b[ 2 ] , ... b[ i - 1 ] , b[ i ] }，a[ i ] 滿足小于等于 i

題目分析：很巧妙的一道構(gòu)造題目，首先通過觀察不難發(fā)現(xiàn)，如果 a[ i ] != a[ i - 1 ] 的話，那么 b[ i ] = a[ i - 1 ] ，因為根據(jù) MEX 前綴的性質(zhì)，如果 MEX{ b[ 1 ] , b[ 2 ] , ... b[ i - 1 ] } = a[ i - 1 ] 的話，那么 a[ i - 1 ] 一定沒有在 b 中出現(xiàn)過，所以如果 a[ i ] != a[ i - 1 ] 時，b[ i ] = a[ i - 1 ]

上面的小結(jié)論解決掉了一部分 b 的賦值，至于剩下的位置，可以貪心來考慮，因為數(shù)組 a 滿足 a[ i ] <= i ，且數(shù)組 a 滿足非降序，所以此時未賦值的 b[ i ] 對應(yīng)著的 a[ i ] 肯定有：a[ i ] == a[ i - 1 ] ，這就意味著 1 ~ n 中一定有在數(shù)組 a 中未出現(xiàn)的元素，貪心策略就是將這些未出現(xiàn)的元素遞增賦值即可

換句話說，假設(shè)數(shù)組 a 的長度為 n ，其中有 m 個不重復的元素（ m <= n ），在經(jīng)過第一段結(jié)論的賦值后，現(xiàn)在數(shù)組 b 中共有 m - 1 個位置已經(jīng)有值了，剩下的 n - m + 1 個位置，剛好對應(yīng)了 n - m 個未出現(xiàn)的元素，以及一個 0

明白原理之后實現(xiàn)起來就比較簡單了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f;const int N=2e5+100;int a[N],b[N];bool vis[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);memset(b,-1,sizeof(b));int n;scanf("%d",&n);a[0]=-1;for(int i=1;i<=n;i++){scanf("%d",a+i);vis[a[i]]=true;if(a[i]!=a[i-1])b[i]=a[i-1];}int cnt=0;for(int i=1;i<=n;i++){if(b[i]!=-1)continue;while(vis[cnt])cnt++;b[i]=cnt++;}for(int i=1;i<=n;i++)printf("%d ",b[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1364C Ehab and Prefix MEX(贪心+构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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