KingdomAndTrees

作者：陈俊锟 汪乐平

关键词：二分 贪心

题目简述

给出一个长度为 $n$ 的正整数序列 $\{a_i\}$（从 0 开始编号），要求确定一个最小的 $k$，使得存在一个正整数序列 $\{b_i\}$，满足对于 $1 \le i < n$ 都有 $b_{i-1} < b_i$，且对于 $0 \le i < n$ 都有 $|a_i-b_i| \le k$。$n \le 50, k\le 10^9$。

算法一

如果存在 $\{b_i\}$ 满足限制 $k$，则其必然满足限制 $k+1$，因此答案具有单调性，我们考虑二分答案。

现在假设我们二分出的答案为 $m$，则我们考虑直接构造一个合法的序列 $\{b_i\}$。那么考虑第 $i$ 位时，就有两种情况（不妨设 $b_{-1} = 0$）：

1. $b_{i-1} < a_i$，那么说明 $b_i=a_i$ 是合法的，为了后面的贪心，我们应该让 $b_i$ 尽量小，因此令 $b_i = \max(b_{i-1}+1, a_i - m)$；

2. $b_{i-1}\ge a_i$，那么说明必须将 $a_i$ 至少增加到 $b_{i-1}+1$，如果 $b_{i-1}+1 - a_i > m$，则判定失败，否则令 $b_i = b_{i-1}+1$。

由于每一步都是尽量使得这一位的 $b_i$ 最小，因此第二步中的“判定为失败”的步骤是正确的，因此本贪心算法是正确的。

时间复杂度：$O(n \log W)$，其中 $W = \max{a_i}$。