使数组非递减的最少硬币数 题解

---

一、题目回顾

给定长度为 $n$ 的数组 $a$。每次操作：

1. 选择一个整数 $k$（$1 \le k \le n$），支付 $k+1$ 枚硬币；
2. 选择 $k$ 个互不相同的下标，将这些位置的值加 $1$。

求使数组变为非递减（$a_1 \le a_2 \le \dots \le a_n$）所需的最少硬币数。

数据范围：$t$ 组测试，$\sum n \le 10^5$，$1 \le a_i \le 10^9$。

---

二、核心思路

2.1 逆序差量

若数组已经有序，答案为 $0$。否则从左到右扫描：

• 遇到 $a_i < a_{i-1}$，则必须将 $a_i$ 提升至少 $d = a_{i-1} - a_i$。不妨令 $a_i := a_{i-1}$（直接填平逆序），并记录差值 $d$。

这样，所有需要填补的"坑"被转化为一系列非负整数 $d_1, d_2, \dots, d_m$，表示对应位置分别需要增加 $d_j$ 次。

2.2 操作模型

每次操作的支出由两部分组成：

• 工作量：实际操作次数 = 该次选中的下标数；
• 固定费用：每次操作额外支付 $1$ 枚硬币。

设所有位置的总增加量为 $S = \sum d_j$，操作总次数为 $T$，则总花费为 $S + T$。

$S$ 是固定的（必须填补的总量），因此最小化总花费等价于最小化操作次数 $T$。

2.3 操作次数下界

每次操作最多给同一位置增加 $1$，因此一个需要增加 $d_j$ 次的位置必须至少参与 $d_j$ 个不同的操作。于是：

$$T \ge \max_{j} d_j$$

同时，$S$ 固定，$T$ 越小越好。能否恰好达到这个下界？可以。

2.4 构造达到下界

令 $M = \max d_j$。我们安排 $M$ 次操作，第 $p$ 次操作（$p = 1, 2, \dots, M$）选择所有满足 $d_j \ge p$ 的位置（即当前还需要增加的位置中，"高度"足够者）。每个位置 $j$ 恰好在前 $d_j$ 次操作中被选中，故总共被增加了 $d_j$ 次。

每次操作的花费 = 选中位置数 $+1$，累加得：

$$\text{总花费} = \left(\sum_{p=1}^{M} \text{第 }p\text{ 次选中的位置数}\right) + M = \sum d_j + M = S + M $$

下界达到，故最小花费即为 $S + M$。

---

三、算法步骤

1. 读入数组 $a$，判断是否已经非递减，是则输出 $0$。
2. 遍历 $i = 2 \dots n$：
   • 若 $a_i < a_{i-1}$，记录差值 $d = a_{i-1} - a_i$，并将 $a_i$ 更新为 $a_{i-1}$。
3. 对所有记录的差值排序（其实只需最大值和总和，排序后方便取 $M$ 和求和）。
4. 输出 $S + M$。

时间复杂度 $O(n \log n)$（排序差值），可优化至 $O(n)$ 仅需最大值与总和。

---

四、AC 代码

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

const int N = 5e5 + 10;

inline int read() {
    int r = 0, w = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r << 3) + (r << 1) + (c ^ 48); c = getchar(); }
    return r * w;
}

int T, n, a[N], b[N];

signed main() {
    T = read();
    while (T--) {
        n = read();
        int tp = 0;
        bool f = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            if (a[i] < a[i - 1]) f = 1;
        }
        if (!f) {
            cout << "0\n";
            continue;
        }

        for (int i = 2; i <= n; ++i) {
            if (a[i] < a[i - 1]) {
                b[++tp] = a[i - 1] - a[i];
                a[i] = a[i - 1];
            }
        }

        sort(b + 1, b + tp + 1);

        int s = 0;
        for (int i = 1; i <= tp; ++i) s += b[i];

        cout << s + b[tp] << "\n";
    }
    return 0;
}