题目内容

游游有一个原始排列，但部分元素丢失，剩余元素形成长度为 $n$ 的数组{$a_1,a_2,…,a_n$}。

对于每个 $1≤i≤n$ ，将前缀 {$a_1,a_2,…,a_i$} 看作新的数组，要把它补全成一个排列，至少需要插入多少个元素？换句话说，对于每个 $1≤i≤n$ ，考虑由前缀 $a_1,a_2,…,a_i$ 构成的元素集合。要将这个集合补全为一个长度为 $m$ 的排列 (即包含 $1,2,…,m$ )， $m$ 的值必须不小于该集合中的任何元素)。为了使插入的元素数量最少，你需要选择一个最优的 $m$ 。请问在这种最优选择下，至少需要插入多少个元素？

请输出每个前缀所需插入的最少元素数。

【名词解释】

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写