ACGO巅峰赛#30 T2

tyc

2026-02-01 23:10:15

发布于：江苏

1阅读

0回复

0点赞

A102287 雾港学宫的时钟塔调度题解

题意

给定整数序列 $(a_1,\dots,a_n)$ 。每次操作可以选择一个位置 (i)，令 $(a_i := a_i + 1)$ 。
要求最终满足严格递增：

$a_1 < a_2 < \cdots < a_n$

问最少需要多少次操作（总加一次数）。

贪心思路

从左到右处理，保证“前缀已经严格递增且代价最小”。

当处理到位置 (i) 时， $(a_1 \sim a_{i-1})$ 已经固定好了，并且之后的操作只能增加 $(a_i)$ ，不能减少，也不能改变前面项。因此：

若 $(a_i > a_{i-1})$ ，不需要操作（加了只会更大，白花次数）。
若 $(a_i \le a_{i-1})$ ，为了满足严格递增，最小需要把它加到：
$a_i' = a_{i-1} + 1$
这样加一次数是最少的（加到更大只会增加操作次数），且不会破坏前面的正确性。

于是每一步的最优调整都是唯一的：

$\text{若 } a_i \le a_{i-1}, \quad \text{操作次数加 } (a_{i-1}+1-a_i), \quad 并令 a_i=a_{i-1}+1$

正确性证明（简述）

对每个 (i)：

由于只能对 $(a_i)$ 做 $+1$ ，如果当前 $(a_i \le a_{i-1})$ ，那么最终必须满足 $(a_i \ge a_{i-1}+1)$ 。
所以把 $(a_i)$ 调到 $(a_{i-1}+1)$ 是必要的下界。
将其调到恰好 $(a_{i-1}+1)$ 所需加一次数最少；若调到更大值会增加操作次数且对后续无额外好处。

因此每步选择都是局部最优且不会影响后续可行性，整体得到全局最优。

复杂度

时间：(O(n))
空间：(O(1))（在原数组上改即可）

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] <= a[i - 1]) {
            long long need = a[i - 1] + 1;
            ans += need - a[i];
            a[i] = need;
        }
    }

    cout << ans << "\n";
    return 0;
}