思路分析
我们的目标是最大化 ∑bi。由于 bi 的定义依赖于前缀 MEX，并且 bi 序列是非递减的（b1≤b2≤...≤bn），我们希望让 bi 的值尽可能早地、尽可能大地增长。
bi=MEX({a1,...,ai})。为了让 bi 的值变大，我们需要让前缀 {a1,...,ai} 尽可能地包含从 0 开始的连续整数。
- 为了最大化 b1=MEX({a1})，我们应该选择 a1=0（如果数组 a 中有 0 的话）。这样 b1=1。如果选择其他数， b1=0。
- 为了最大化 b2=MEX({a1,a2})，在 a1=0 的基础上，我们应该选择 a2=1（如果数组 a 中有 1 的话）。这样 {a1,a2}={0,1}，使得 b2=2。
- 以此类推，为了让 bi 达到最大可能值 i，我们需要让前缀 {a1,...,ai} 恰好是 {0,1,...,i−1}。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
