B3723 [语言月赛202303] Coin Selection G
一扶苏一
·
·
题解
[语言月赛202303] Coin Selection G 题解
Source & Knowledge
2023 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。
本题考察循环结构。
文字题解
题目大意
小 F 和小 B 玩游戏。初始时，他们有 0 元钱。桌子上有 n 枚硬币，第 i 枚硬币的价值是 a_i 元。
双方交替操作，每次双方在桌面上剩余的硬币中，选择不超过手中钱数的硬币里价值最高的那个硬币，拿到手里。
如果没有硬币不超过手里的钱数，则选择价值最低的硬币。
求游戏结束时双方手里的钱数。
### 解析
依题意模拟。
注意到一共会进行 $n$ 次操作，可以用一个长度为 $n$ 的循环依次来进行每次取硬币。每次一个硬币被拿走后，可以把它对应的 $a_i$ 改为 $0$，标记为它已经被拿走了。
可以发现，当 $i$ 是奇数时，小 F 操作，否则小 B 操作。于是可以通过 $i$ 的奇偶性判断当前的操作的玩家。
```cpp
for (int i = 1; i <= n; ++i) {
if (i % 2 == 1) { // 小 F 操作
} else { // 小 B 操作
}
}
```
接下来，以小 F 操作为例，介绍如何找到当前选择的硬币。
首先用一个全局变量 $sa$ 维护小 F 当前手里的钱数。然后扫描一遍数组，维护一个变量 $pos$，它的含义是在已扫描的元素里不大于 $sa$ 的那些硬币里价值最大的的硬币的**所在下标**。可以用类似打擂台的形式求出 $pos$：
```cpp
int pos = 0;
for (int j = 1; j <= n; ++j) if (a[j] <= sa) {
if (a[pos] < a[j]) pos = j;
}
```
注意到如果如果所有硬币都比 $sa$ 大，那么上面的循环结束后 $pos$ 仍然为 $0$。此时我们需要在剩余硬币中找到那个不为 $0$ 且最小的：
```cpp
if (pos == 0) {
for (int j = 1; j <= n; ++j) if (a[pos] == 0) {
pos = j;
} else if (a[j] > 0 && a[pos] > a[j]) pos = j;
}
```
至此，我们就找到了这次所拿的硬币的下标 $pos$。只需要给 $sa$ 加上 $a_{pos}$ 再把 $a_{pos}$ 置零即可：
```cpp
sa += a[pos]; a[pos] = 0;
```
类似的，可以完成小 F 对应的操作代码，把二者填充到上面的 for 循环中，就完成了题目的主体。
观察数据范围：$1 \leq a_i \leq 10^{16}$，显然 $a_i$ 应该用 `long long` 来存。那么 $sa$ 呢？注意到每个人至多拿 $\frac{n}{2}$（向上取整）个硬币，也就是最多拿 $500$ 枚硬币，所以 $sa$ 不超过 $5 \times 10^{18}$。而 `long long` 的上界是 $9 \times 10^{18}$，所以 $sa$ 也可以用 `long long` 存下。
## 视频题解
**完整代码请在视频中观看**。
