自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:38，当前版本为作者最后更新于2018-05-20 19:49:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202303] Coin Selection G 题解

Source & Knowledge

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

本题考察循环结构。

文字题解

题目大意

小 F 和小 B 玩游戏。初始时，他们有 $0$ 元钱。桌子上有 $n$ 枚硬币，第 $i$ 枚硬币的价值是 $a_i$ 元。

双方交替操作，每次双方在桌面上剩余的硬币中，选择不超过手中钱数的硬币里价值最高的那个硬币，拿到手里。
如果没有硬币不超过手里的钱数，则选择价值最低的硬币。

求游戏结束时双方手里的钱数。

$1 \leq n \le 10^3$，$1 \leq a_i \le 10^{16}$。

解析

依题意模拟。

注意到一共会进行 $n$ 次操作，可以用一个长度为 $n$ 的循环依次来进行每次取硬币。每次一个硬币被拿走后，可以把它对应的 $a_i$ 改为 $0$，标记为它已经被拿走了。

可以发现，当 $i$ 是奇数时，小 F 操作，否则小 B 操作。于是可以通过 $i$ 的奇偶性判断当前的操作的玩家。

for (int i = 1; i <= n; ++i) {
  if (i % 2 == 1) { // 小 F 操作

  } else {          // 小 B 操作

  }
}

接下来，以小 F 操作为例，介绍如何找到当前选择的硬币。

首先用一个全局变量 $sa$ 维护小 F 当前手里的钱数。然后扫描一遍数组，维护一个变量 $pos$，它的含义是在已扫描的元素里不大于 $sa$ 的那些硬币里价值最大的的硬币的所在下标。可以用类似打擂台的形式求出 $pos$：

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$ 且最小的：

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}$ 置零即可：

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 存下。

视频题解

完整代码请在视频中观看。