102902: [Atcoder]ABC290 C - Max MEX
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：6
Solved：0
Description
Score : $300$ points
Problem Statement
You are given a length-$N$ sequence of non-negative integers.
When $B$ is a sequence obtained by choosing $K$ elements from $A$ and concatenating them without changing the order, find the maximum possible value of $MEX(B)$.
Here, for a sequence $X$, we define $MEX(X)$ as the unique non-negative integer $m$ that satisfies the following conditions:
- Every integer $i$ such that $0 \le i < m$ is contained in $X$.
- $m$ is not contained in $X$.
Constraints
- All values in the input are integers.
- $1 \le K \le N \le 3 \times 10^5$
- $0 \le A_i \le 10^9$
Input
The input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer.
Sample Input 1
7 3 2 0 2 3 2 1 9
Sample Output 1
3
In this input, $A=(2,0,2,3,2,1,9)$, and you obtain the sequence $B$ by picking $K=3$ elements. For example,
- If the $1$-st, $2$-nd, and $3$-rd elements are chosen, $MEX(B)=MEX(2,0,2)=1$.
- If the $3$-rd, $4$-th, and $6$-th elements are chosen, $MEX(B)=MEX(2,3,1)=0$.
- If the $2$-nd, $6$-th, and $7$-th elements are chosen, $MEX(B)=MEX(0,1,9)=2$.
- If the $2$-nd, $3$-rd, and $6$-th elements are chosen, $MEX(B)=MEX(0,2,1)=3$.
The maximum possible $MEX$ is $3$.
Input
题意翻译
给出一个长度为 $N$ 的仅含非负整数的序列 $A$，你需要从中选出 $K$ 个数使得这 $K$ 个数的 Mex 最大，其中 Mex 为未出现的最小非负整数。 $1\leq K\leq N\leq 3\times 10^5$，$0\leq A_i\leq 10^9$。Output
得分：300分
部分
问题描述
给你一个长度为 N 的非负整数序列 A 。
当 B 是通过从 A 中选择 K 个元素并按原顺序连接得到的序列时，找出 MEX(B) 的最大可能值。 这里，对于一个序列 X ，我们定义 MEX(X) 为满足以下条件的唯一非负整数 m ：
- 每个满足 0 ≤ i < m 的整数 i 都包含在 X 中。 - m 不包含在 X 中。 部分 约束条件 - 输入中的所有值都是整数。 - $1 \le K \le N \le 3 \times 10^5$ - $0 \le A_i \le 10^9$ 部分 输入格式 输入从标准输入以以下格式给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$ 部分 输出格式 输出答案。 部分 样例输入 1 7 3 2 0 2 3 2 1 9 部分 样例输出 1 3 在这个输入中，$A=(2,0,2,3,2,1,9)$，你可以通过选择 K=3 个元素得到序列 B 。例如， - 如果选择第 1 个、第 2 个和第 3 个元素，$MEX(B)=MEX(2,0,2)=1$。 - 如果选择第 3 个、第 4 个和第 6 个元素，$MEX(B)=MEX(2,3,1)=0$。 - 如果选择第 2 个、第 6 个和第 7 个元素，$MEX(B)=MEX(0,1,9)=2$。 - 如果选择第 2 个、第 3 个和第 6 个元素，$MEX(B)=MEX(0,2,1)=3$。 最大的可能 MEX 是 3。
当 B 是通过从 A 中选择 K 个元素并按原顺序连接得到的序列时，找出 MEX(B) 的最大可能值。 这里，对于一个序列 X ，我们定义 MEX(X) 为满足以下条件的唯一非负整数 m ：
- 每个满足 0 ≤ i < m 的整数 i 都包含在 X 中。 - m 不包含在 X 中。 部分 约束条件 - 输入中的所有值都是整数。 - $1 \le K \le N \le 3 \times 10^5$ - $0 \le A_i \le 10^9$ 部分 输入格式 输入从标准输入以以下格式给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$ 部分 输出格式 输出答案。 部分 样例输入 1 7 3 2 0 2 3 2 1 9 部分 样例输出 1 3 在这个输入中，$A=(2,0,2,3,2,1,9)$，你可以通过选择 K=3 个元素得到序列 B 。例如， - 如果选择第 1 个、第 2 个和第 3 个元素，$MEX(B)=MEX(2,0,2)=1$。 - 如果选择第 3 个、第 4 个和第 6 个元素，$MEX(B)=MEX(2,3,1)=0$。 - 如果选择第 2 个、第 6 个和第 7 个元素，$MEX(B)=MEX(0,1,9)=2$。 - 如果选择第 2 个、第 3 个和第 6 个元素，$MEX(B)=MEX(0,2,1)=3$。 最大的可能 MEX 是 3。