题目解析

问题重述

有 $n$ 个宝箱，第 $i$ 个宝箱初始有 $a_i$ 枚硬币。你可以向任意宝箱添加非负整数数量的硬币，但添加后所有宝箱的硬币总数必须至少为 $k$。

然后 Monocarp 会贪婪地取宝箱：每次选择当前硬币数最多的宝箱，直到取到的硬币总数 $\ge k$ 为止。

你需要通过添加硬币，使得 Monocarp 停止时取到的硬币数恰好等于 $k$。求最少需要添加多少硬币。

关键思路

核心观察： 假设我们不添加任何硬币，Monocarp 会按照初始硬币数从大到小依次取宝箱。设他取完若干个最大宝箱后，总数为 $s$，且 $s \le k$，但再取下一个宝箱就会超过 $k$。此时，如果我们将目前取到的宝箱中最大的那个增加 $k-s$ 枚硬币，那么：

• 这组宝箱的总数变为 $s + (k-s) = k$
• 由于最大宝箱变大了，它仍会被先取到，且取完这组宝箱后总数刚好 $k$，Monocarp 就会停止
• 添加的硬币数就是 $k-s$

为什么只考虑增大当前已取宝箱中的最大值？

假设我们试图增大某个不在当前集合中的宝箱 $i$（初始值为 $a_i$），使得它代替集合中的某个宝箱 $j$（$a_j > a_i$）被取到。为了让宝箱 $i$ 在 $j$ 之前被取，必须满足 $a_i + x \ge a_j$，需要添加 $x \ge a_j - a_i$。而如果我们直接增大宝箱 $j$，添加更少的硬币（$k-s$）就能达到目的。因此，改变取宝箱的顺序不是最优的。

结论： 最优策略是：

1. 将 $a$ 从大到小排序
2. 从大到小累加，找到最大的 $s \le k$，即取前若干个最大宝箱，使得总和不超过 $k$ 但再加下一个就会超过
3. 答案就是 $k - s$

算法步骤

1. 读入 $t$ 个测试用例
2. 对每个测试用例：
   • 读入 $n$ 和 $k$
   • 读入数组 $a$，长度为 $n$
   • 将 $a$ 按从大到小排序
   • 初始化 $sum = 0$
   • 遍历排序后的数组：
     • 如果 $sum + a[i] \le k$，则 $sum += a[i]$
     • 否则跳出循环
   • 输出 $k - sum$

时间复杂度

排序：$O(n \log n)$，$n \le 50$，非常快。 总复杂度：$O(t \cdot n \log n)$

示例验证

例1： $n=5, k=4, a=[4,1,2,3,2]$

• 排序降序：$[4,3,2,2,1]$
• 取 $4$，$sum=4 \le k$，下一个 $3$ 会使 $sum=7>4$，停止
• $ans = 4-4=0$

例2： $n=5, k=10, a=[4,1,2,3,2]$

• 排序降序：$[4,3,2,2,1]$
• 取 $4$，$sum=4$；取 $3$，$sum=7$；取 $2$，$sum=9$；下一个 $2$ 会使 $sum=11>10$，停止
• $ans = 10-9=1$

例3： $n=2, k=10, a=[1,1]$

• 排序降序：$[1,1]$
• 取 $1$，$sum=1$；取 $1$，$sum=2$；结束（没有更多宝箱）
• $ans = 10-2=8$

例4： $n=3, k=8, a=[3,3,3]$

• 排序降序：$[3,3,3]$
• 取 $3$，$sum=3$；取 $3$，$sum=6$；下一个 $3$ 会使 $sum=9>8$，停止
• $ans = 8-6=2$

C++ 代码

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

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 按从大到小排序
        sort(a.begin(), a.end(), greater<int>());
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum + a[i] <= k) {
                sum += a[i];
            } else {
                break;
            }
        }
        
        cout << k - sum << '\n';
    }
    
    return 0;
}