A102287 雾港学宫的时钟塔调度 题解
题意
给定整数序列(a1,…,an)(a_1,\dots,a_n)(a1 ,…,an )。每次操作可以选择一个位置 (i)，令 (ai:=ai+1)(a_i := a_i + 1)(ai :=ai +1)。
要求最终满足严格递增：
a1<a2<⋯<ana_1 < a_2 < \cdots < a_n a1 <a2 <⋯<an
问最少需要多少次操作（总加一次数）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
贪心思路
从左到右处理，保证“前缀已经严格递增且代价最小”。
当处理到位置 (i) 时，(a1∼ai−1)(a_1 \sim a_{i-1})(a1 ∼ai−1 ) 已经固定好了，并且之后的操作只能增加 (ai)(a_i)(ai )，不能减少，也不能改变前面项。因此：
* 若(ai>ai−1)(a_i > a_{i-1})(ai >ai−1 )，不需要操作（加了只会更大，白花次数）。
* 若 (ai≤ai−1)(a_i \le a_{i-1})(ai ≤ai−1 )，为了满足严格递增，最小需要把它加到：
ai′=ai−1+1a_i' = a_{i-1} + 1 ai′ =ai−1 +1
这样加一次数是最少的（加到更大只会增加操作次数），且不会破坏前面的正确性。
于是每一步的最优调整都是唯一的：
若 ai≤ai−1,操作次数加 (ai−1+1−ai),并令ai=ai−1+1\text{若 } a_i \le a_{i-1}, \quad \text{操作次数加 } (a_{i-1}+1-a_i), \quad 并令 a_i=a_{i-1}+1 若 ai ≤ai−1 ,操作次数加 (ai−1 +1−ai ),并令ai =ai−1 +1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正确性证明（简述）
对每个 (i)：
1. 由于只能对 (ai)(a_i)(ai ) 做 +1+1+1，如果当前 (ai≤ai−1)(a_i \le a_{i-1})(ai ≤ai−1 )，那么最终必须满足 (ai≥ai−1+1)(a_i \ge a_{i-1}+1)(ai ≥ai−1 +1)。
所以把 (ai)(a_i)(ai ) 调到 (ai−1+1)(a_{i-1}+1)(ai−1 +1) 是必要的下界。
2. 将其调到恰好 (ai−1+1)(a_{i-1}+1)(ai−1 +1) 所需加一次数最少；若调到更大值会增加操作次数且对后续无额外好处。
因此每步选择都是局部最优且不会影响后续可行性，整体得到全局最优。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复杂度
* 时间：(O(n))
* 空间：(O(1))（在原数组上改即可）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例解释
输入：3 3 2 2 10
* 第 2 个：3 不大于 3 → 调到 4，+1
* 第 3 个：2 不大于 4 → 调到 5，+3
* 第 4 个：2 不大于 5 → 调到 6，+4
* 第 5 个：10 > 6，无需改
总次数：(1+3+4=8)
