自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:17:00，当前版本为作者最后更新于2025-03-05 10:54:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考察贪心。

首先，我们需要将所有求助者的金额按照从小到大的顺序进行排列。这一步的目的是确保在后续选择时，能够优先处理金额较小的需求，为后续的贪心策略打下基础。接下来，采用贪心算法依次累加金额：从最小的金额开始逐个累加，直到总额即将超过阿飞的预算为止。此时累计的人数就是所能帮助的最大数量。

时间复杂度主要在排序部分，采用标准库的 std::sort，为 $O(n \log n)$。若是使用冒泡、选择、插入排序则为 $O(n^2)$。对于 $n \le 500$ 来说，运行效率是完全满足要求的。

参考代码（只展示关键部分）：

sort(x, x + n);
int cnt = 0;  // 帮助的人数
int sum = 0;  // 当前已使用的钱数
// 从最小的需求开始依次累加
for (int i = 0; i < n; i++) {
    if (sum + x[i] <= w) {
        sum += x[i];
        cnt++;
    } else {
        break; // 一旦加上当前需求超出 w，就退出循环
    }
}