D. 避开最小值 题解

---

一、题意理解

我们有一个数组 $a$，每次操作可以选择一个元素 $a_i$ 加 $1$，最多进行 $k$ 次操作。目标是使所有元素相等。

• 如果某次操作选择的 $a_i$ 严格大于当前数组的最小值，则获得一枚硬币（称为"好操作"）。
• 如果选择的 $a_i$ 等于当前数组的最小值，则不获得硬币（称为"坏操作"）。

求在所有能使数组全等的策略中，最多能获得多少硬币。

---

二、核心观察

2.1 最终值 $v$ 应尽可能大

设最终所有元素都等于 $v$。

结论：使 $v$ 尽可能大总是最优的。

证明：

假设存在一个最优策略，最终数组全部等于 $v - 1$，获得硬币数为 $P(v-1)$。

我们可以这样构造一个到达 $v$ 的策略：

1. 先按最优策略将所有元素变为 $v - 1$；
2. 然后对每个元素依次执行一次 $+1$ 操作，使全部变为 $v$。

在步骤 $2$ 中，当增加某个元素时，由于当前数组中所有元素都等于 $v-1$（即全部相等），不存在严格大于最小值的元素，因此所有新增操作都是"坏操作"，不会获得硬币。

因此：

$$P(v) \geq P(v-1)$$

即较高目标值的最大收益不低于较低目标值。由此可知，最大化 $v$ 总是最优的。

---

2.2 计算最大可行的 $v$

总操作次数不能超过 $k$。将所有元素变为 $v$ 需要增加的总量为：

$$\sum_{i=1}^{n} (v - a_i) = n \cdot v - \sum_{i=1}^{n} a_i $$

需要满足：

$$n \cdot v - \sum_{i=1}^{n} a_i \leq k$$

解得最大可行的 $v$ 为：

$$\boxed{ v = \left\lfloor \frac{k + \sum_{i=1}^{n} a_i}{n} \right\rfloor } $$

同时还需满足 $v \geq \max(a_i)$，否则某些元素需要被减少，但操作只能增加，无法完成目标。

若 $v < \max(a_i)$，则输出 $-1$。

---

三、最大化硬币数（好操作数）

当目标值 $v$ 确定后，总操作次数为定值：

$$\text{总操作数} = n \cdot v - \sum_{i=1}^{n} a_i$$

因此，最大化好操作数 等价于 最小化坏操作数。

---

3.1 坏操作数的下界

什么样的操作必然是坏操作？

来源一：初始最小值

设初始数组的最小值为 $m_0 = \min(a)$。

初始时，值为 $m_0$ 的那些元素如果要被增加，第一次对它们进行操作时，它们等于当前最小值，因此是坏操作。

设有 $c$ 个元素等于 $m_0$，则至少需要 $c$ 次坏操作来"启动"它们（每次只能启动一个，因为一旦某个 $m_0$ 被增加，最小值可能发生变化）。

来源二：最小值的"爬升"过程

数组的最小值要从 $m_0$ 逐步增加到 $v$。在最小值变为 $m_0 + 1, m_0 + 2, \dots, v-1$ 的每个中间值上，至少存在一个元素等于该值且被操作时它是当前最小值，因此每个中间值至少对应一次坏操作。

中间值的个数为 $(v - m_0)$，但目标值 $v$ 本身不需要被增加（已经是最终值），所以中间值个数为 $v - m_0$，其中最小值为 $m_0$ 的那个"台阶"已在来源一中计算过一部分。

更精确地：最小值需要经历的值有：$m_0, m_0+1, \dots, v-1$。对于 $m_0$，需要 $c$ 次坏操作（启动所有初始最小值）；对于 $m_0+1$ 到 $v-1$，每个值至少 $1$ 次坏操作。

因此，坏操作总数至少为：

$$\boxed{ \text{bad}_{\min} = c + (v - m_0 - 1) = (v - m_0) + (c - 1) } $$

其中 $c$ 是初始数组中等于 $m_0$ 的元素个数。

若 $v = m_0$（即不需要操作），则坏操作数为 $0$。

---

3.2 达到下界的贪心策略

我们可以通过以下贪心策略达到这个下界：

将元素按从大到小的顺序依次增加到 $v$。

• 先处理较大的元素，此时最小值仍为初始最小值 $m_0$，对这些较大元素的操作都满足 $a_i > m_0$，因此全部是好操作。
• 最后处理初始等于 $m_0$ 的那些元素。此时其他元素已经增加到 $v$（或至少大于 $m_0$），最小值可能是某个略高于 $m_0$ 的值，但处理 $m_0$ 类元素时，需要先让最小值逐步"爬升"到 $v$，这与下界分析一致。

该策略可达到理论下界。

---

四、最终公式

总操作数：

$$\text{total} = n \cdot v - \sum_{i=1}^{n} a_i$$

最小坏操作数（当 $v > m_0$ 时）：

$$\text{bad} = (v - m_0) + (c - 1)$$

其中 $c$ 为 $a$ 中等于 $m_0$ 的元素个数。

当 $v = m_0$ 时：

$$\text{bad} = 0$$

最大好操作数（硬币数）：

$$\boxed{ \text{ans} = \text{total} - \text{bad} }$$

展开后：

$$\begin{aligned} \text{ans} &= \left( n \cdot v - \sum a_i \right) - \left[ (v - m_0) + (c - 1) \right] \\[4pt] &= \sum_{i=1}^{n} (v - a_i) - (v - m_0) - (c - 1) \end{aligned} $$

---

五、标程解析

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toLong() }
        val a = readln().split(' ').map { it.toLong() }
        
        // 计算最大可行的目标值 v
        val resVal = (k + a.sum()) / n
        if (resVal < a.maxOrNull()!!) {
            println(-1)
            return@repeat
        }
        
        val minEl = a.minOrNull()!!
        // ans = 总操作数 - 坏操作数
        var ans = a.sumOf { resVal - it } - (resVal - minEl)
        if (minEl < resVal)
            ans -= a.count { it == minEl } - 1
        println(ans)
    }
}

步骤解析：

1. 读入 $n, k$ 和数组 $a$。
2. 计算最大目标值 $v = \lfloor (k + \sum a_i) / n \rfloor$。
3. 若 $v < \max(a_i)$，输出 $-1$。
4. 计算答案：
   • a.sumOf { resVal - it } 为总操作数 $\sum (v - a_i)$；
   • 减去 $(v - \min(a))$ 对应最小值的"爬升"过程坏操作；
   • 若 $\min(a) < v$，还需减去 $(c - 1)$，因为启动 $c$ 个初始最小值需要 $c$ 次坏操作，其中 $1$ 次已包含在 $(v - \min(a))$ 中，剩余 $c-1$ 次需额外减去。
5. 输出答案。

---

六、样例验证

样例 1

输入：

3 16
1 10 2

• $\sum a = 13$，$v = \lfloor (16 + 13) / 3 \rfloor = 9$
• $\max(a) = 10$，$v = 9 < 10$ → 输出 $-1$ ✅

样例 2

输入：

4 20
6 2 4 9

• $\sum a = 21$，$v = \lfloor (20 + 21) / 4 \rfloor = 10$
• $v = 10 \geq \max(a) = 9$ ✓
• 总操作数 $= \sum (10 - a_i) = 4 + 8 + 6 + 1 = 19$
• $\min(a) = 2$，$c = 1$（只有一个 $2$）
• 坏操作数 $= (10 - 2) + (1 - 1) = 8$
• 答案 $= 19 - 8 = 11$ ✅

样例 3

输入：

5 9
7 7 7 7 7

• $\sum a = 35$，$v = \lfloor (9 + 35) / 5 \rfloor = 8$
• $v = 8 \geq 7$ ✓
• $\min = 7 = v$，直接输出 $0$ ✅

样例 4

输入：

2 1000000000000
1000000000 1000000000

• $\sum a = 2 \times 10^9$，$v = \lfloor (10^{12} + 2 \times 10^9) / 2 \rfloor = 501 \times 10^9 = 5.01 \times 10^{11}$
• $v \geq 10^9$ ✓
• 总操作数 $= 2 \times (5.01 \times 10^{11} - 10^9) \approx 10^{12}$
• $\min = 10^9$，$c = 2$
• 坏操作数 $= (5.01 \times 10^{11} - 10^9) + (2 - 1) \approx 5 \times 10^{11} + 1$
• 答案 $= 10^{12} - 5 \times 10^{11} - 1 = 499999999999$ ✅

---

七、代码实现（C++）

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

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    ll v = (k + sum) / n;
    ll mx = *max_element(a.begin(), a.end());
    
    if (v < mx) {
        cout << "-1\n";
        return;
    }
    
    ll mn = *min_element(a.begin(), a.end());
    ll c = count(a.begin(), a.end(), mn);
    
    ll total_ops = n * v - sum;     // 总操作数
    ll bad_ops = 0;
    if (v > mn) {
        bad_ops = (v - mn) + (c - 1);  // 最小坏操作数
    }
    
    ll ans = total_ops - bad_ops;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

八、复杂度分析

• 每个测试用例需遍历数组一次，时间复杂度 $O(n)$。
• 所有测试用例 $n$ 之和 $\leq 3 \times 10^5$，整体可行。
• 空间复杂度 $O(n)$。