CF1364C Ehab and Prefix MEXs 【贪心，构造】

原题链接

题面

思路

这是一道贪心构造题

首先是-1的情况：通过举例子可以发现，当 $a_i$ 大于等于 $i$ 时，一定是无解的；

然后题目保证了给的一定是一个升序列，但是可能会有相同的数，举个 1 2 2 2 3 的例子，答案应该是 0 1 4 5 2 ，在处理和前一个相同的数字时，可以使用序列中没有出现过的数，可以发现这样并不影响后面的结果，对于和前面不一样的数，就是用该数前面一个数，刚好就相当于给当前这一位垫上来了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
map<int, int> ma;
int main()
{
    int n;cin >> n;bool f = 0;for (int i = 1; i <= n; i ++ ){
    cin >> a[i];ma[a[i]] = 1;if (a[i] < a[i - 1] || a[i] > i) //处理 -1 的情况{
    f= 1;}}if (f) cout << -1 << endl;else{
    vector<int> v;for (int i = 1; i <= n * 2; i ++ ) //存储没有出现过的数{
    if (!ma[i]) v.push_back(i);}int c = 0;for (int i = 1; i <= n; i ++ ) //按思路进行{
    if (a[i] == a[i - 1]) cout << v[c ++ ] << " ";else cout << a[i - 1] << " ";}}return 0;
}

总结

这样的构造体真是十分巧妙，对于我这种思维能力还不太行的人来说就是要花大量时间去推敲，然后再把题量堆上去，自然而然也就能得到提升了。