Codeforces 1364C - Ehab and Prefix MEXs

题意:给1e5的数组a 保证 ai <= ai+1 ai<=i

　　求一个一样长的数组b 使得mex(b1,b2···bi) = ai

QAQ:不知道为啥这1600分的题比赛时出不了啊啊啊啊啊啊啊啊

题解:其实比赛的时候就知道当前bi填的数字肯定是0,1,2...a[i] - 1中第一个没出现的数字

　　如果已经被填满了就在a[i] + 1...a[n]-1中填第一个后面没出现的数字

　　因为显然有一个限制你当前填的数字不能等于后面的某一个a[i]

　　比赛的时候一直想一些奇奇怪怪的实现方法.. 越整越麻烦

　　显然bi要填满的数字就是0-a[n]-1

　　把数字分成两组一组是a[i]中出现的一组是没出现的分别维护指针

　　如果a[i] > 第一组的数字就填第二组的 ... 都填完了就选inf

　　填完再判断一下合法性

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <string.h>

#include <queue>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

const int MAXN = 1e5 + 5;

int val[100015];

int a[MAXN];

int b[MAXN];

int c[MAXN];

int d[MAXN];

int main() {

    int cn1 = 0, cn2 = 0;

    int n;

    cin>>n;

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), val[a[i]]++;

    for(int i = 0; i < a[n]; i++)

        if(!val[i]) d[++cn2] = i;

        else c[++cn1] = i;

    int nl = 1, nr = 1;

    for(int i = 1; i <= n; i++) {

        if(nl <= cn1 && a[i] > c[nl]) b[i] = c[nl++];

        else if(nr <= cn2) b[i] = d[nr++];

        else b[i] = n + 5;

    }

    memset(val, 0, sizeof(val));

    int now = -1;

    for(int i = 1; i <= n; i++) {

        val[b[i]] = 1;

        while(val[now + 1]) now += 1;

        if(now + 1 != a[i]) {

            puts("-1");

            return 0;

        }

    }

    for(int i = 1; i <= n; i++) printf("%d ", b[i]); puts("");

    return 0;

}

巴特西

Codeforces 1364C - Ehab and Prefix MEXs

最新文章

热门文章