[题解]Mail.Ru Cup 2018 Round 1

【题目】

【描述】

Ildar定义了一种方法，可以由一个数组产生一个数。具体地，从这个数组中任选一个子集，不在这个子集中的最小的非负整数称为mex，就是由这个数组得到的数。初始时刻Ildar的数组是一个空数组，通过上述方法得到某个mex，加入到数组的尾端，不断重复以上操作。现在给你一个n长的数组a，问Ildar能否得到这个数组，如果能则输出-1，否则输出最小的整数t，表示数组的前t个数中至少有一个数不能得到。

数据范围：1<=n<=100000，0<=a[i]<=10^9

【思路】

要想得到数字0，可以选择空集作为子集；要想得到数字k，选择的子集必须包含{0,1,...,k-1}。于是，从前往后扫给的数组a，当前的数字最多能比之前出现过的数字大1，否则这个数字是不能被得到的，当前位置就是t。

【我的实现】

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6

 7 using namespace std;

 8 #define MaxN 100020

 9 int a[MaxN];

10

11 int main()

12 {

13     int n, x;

14     int cur = -1;

15     scanf("%d", &n);

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

17     {

18         scanf("%d", &x);

19         if(x > cur + 1)

20         {

21             printf("%d", i);

22             return 0;

23         }

24         cur = max(cur, x);

25     }

26     printf("-1");

27     return 0;

28 }

【评测结果】

巴特西

[题解]Mail.Ru Cup 2018 Round 1 - B. Appending Mex

最新文章

热门文章