自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:16:03，当前版本为作者最后更新于2024-02-21 00:15:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Source & Knowledge

2024 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

$n$ 个牛棚，编号为 $1 \sim n$。初始时防御值分别为 $a_1, a_2, \cdots, a_n$。有 $t$ 份补给，每份每份补给可以为某一个牛棚提供额外的 $1$ 点防御值。一个牛棚可以接受多份补给。

补给完成后，有 $m$ 块陨石分别撞击 $x_1, x_2, \cdots, x_n$ 号牛棚，每次撞击会令对应牛棚防御值减少 $2$ 点。当一间牛棚的防御值 $\leq 0$ 时，牛棚会被破坏。

目前想要让被破坏的牛棚尽可能少。求在最优的补给策略下，被破坏的牛棚的最少的数量。

题目分析

不妨换一个角度来考虑。我们先让陨石撞击牛棚，计算出撞击后的牛棚的原始防御值，之后计算需要多少补给才能让某个牛棚不被破坏。即，我们计算每个牛棚的 $a_i - d_i$，并与 $1$（$1$ 是牛棚不被破坏的最少防御值）做比较。其中 $d_i$ 代表每个牛棚因陨石而损失的防御值。

在计算时，可以直接枚举陨石，并直接在 $a$ 数组中做操作。核心代码如下：

for (int i = 1; i <= m; ++i) {
    int x;
    cin >> x;
    a[x] -= 2;
}

可以很显然地考虑到，当 $a_i - d_i < 1$ 时，我们需要补给这个牛棚，补给的数量是 $1 - (a_i - d_i)$。在补给有限的情况下，如果想要让尽可能多的牛棚存活，那显然需要优先补给 $1 - (a_i - d_i)$ 更小的牛棚。

因此，可以使用冒泡排序等方法，将 $1 - (a_i - d_i)$ 由小到大排序（或将 $(a_i - d_i)$ 由大到小排序也可，核心思路是一致的）。

for (int i = 1; i <= n; ++i) {
    a[i] = 1 - a[i]; // 此处 a[i] 已经减去了损失值，直接覆写
    // 代表需要的补给数量
}

// 冒泡排序
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < n; ++j) {
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);
	}
}

排序后，开始分配补给。从前往后枚举 $i$，判断每个牛棚的 $1 - (a_i - d_i)$ 是否大于 $0$（即需要补给）。如果小于等于 $0$，代表不需要补给，直接跳过；如果大于 $0$，判断当前剩余的补给是否够填补上 $1 - (a_i - d_i)$，如果足够则直接减去，否则中止补给。

在过程中，遇到「不需要补给」和「补给成功」的牛棚，同时计数即可。

int ans = 0;
for (int i = 1; i <= n; ++i) {
    // a[i] 代表需要的补给数量，上方已经覆写
    if (a[i] <= 0) { // 不需要补给
    	ans++;
    } else {
        if (t >= a[i]) { // 剩余的 t 足够补给该牛棚
            t -= a[i]; // 减去补给该牛棚的消耗
            ans++;
        } else break; // 否则直接中断循环，因为后面的补给量只会越来越大，一定无法补给成功
    }
}
cout << ans << endl;

视频讲解