第2题-最大化前缀空缺数 - problem_ide

访问过于频繁

您的访问过于频繁，请稍后再试。

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路分析

我们的目标是最大化 $\sum \operatorname{vac}(i)$ 。由于 $\operatorname{vac}(i)$ 的定义依赖于前缀空缺数，并且 $\operatorname{vac}(i)$ 序列是非递减的（ $\operatorname{vac}(1) \le \operatorname{vac}(2) \le \dots \le \operatorname{vac}(n)$ ），我们希望让 $\operatorname{vac}(i)$ 的值尽可能早地、尽可能大地增长。

$\operatorname{vac}(i)$ 的值等于集合 $\{x_1, \dots, x_i\}$ 中未出现的最小非负整数。为了让 $\operatorname{vac}(i)$ 的值变大，我们需要让前缀 $\{x_1, \dots, x_i\}$ 尽可能地包含从 $0$ 开始的连续整数。

为了最大化 $\operatorname{vac}(1)$ ，我们应该选择 $x_1=0$ （如果给定的元素中有 $0$ 的话）。这样 $\operatorname{vac}(1)=1$ 。如果选择其他数， $\operatorname{vac}(1)=0$ 。
为了最大化 $\operatorname{vac}(2)$ ，在 $x_1=0$ 的基础上，我们应该选择 $x_2=1$ （如果给定的元素中有 $1$ 的话）。这样 $\{x_1, x_2\} = \{0, 1\}$ ，使得 $\operatorname{vac}(2)=2$ 。
以此类推，为了让 $\operatorname{vac}(i)$ 达到最大可能值 $i$ ，我们需要让前缀 $\{x_1, \dots, x_i\}$ 恰好是 $\{0, 1, \dots, i-1\}$ 。

编辑器加载中…

输入

预期输出（选填）

思路分析

P3583.第2题-最大化前缀空缺数

Status

Development

Support

About

Status

Development

Support

About

Don't have an account?

SIGN IN