B3938 [语言月赛 202402] 陨石 题解
Maxmilite
·
·
题解
Source & Knowledge
2024 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
补给完成后，有 $m$ 块陨石分别撞击 $x_1, x_2, \cdots, x_n$ 号牛棚，每次撞击会令对应牛棚防御值减少 $2$ 点。当一间牛棚的防御值 $\leq 0$ 时，牛棚会被破坏。
目前想要让被破坏的牛棚尽可能少。求在最优的补给策略下，被破坏的牛棚的最少的数量。
## 题目分析
不妨换一个角度来考虑。我们先让陨石撞击牛棚，计算出撞击后的牛棚的原始防御值，之后计算需要多少补给才能让某个牛棚不被破坏。即，我们计算每个牛棚的 $a_i - d_i$，并与 $1$（$1$ 是牛棚不被破坏的最少防御值）做比较。其中 $d_i$ 代表每个牛棚因陨石而损失的防御值。
在计算时，可以直接枚举陨石，并直接在 $a$ 数组中做操作。核心代码如下：
```cpp
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)$ 由大到小排序也可，核心思路是一致的）。
```cpp
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)$，如果足够则直接减去，否则中止补给。
在过程中，遇到「不需要补给」和「补给成功」的牛棚，同时计数即可。
```cpp
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;
```
## 视频讲解
