CF1879F Last Man Standing

在一款电子游戏中有 $n$ 个英雄。每个英雄有一个生命值 $h$ 和初始护甲值 $a$。当前护甲值记为 $a_{\mathit{cur}}$，初始时等于 $a$。 当一个英雄受到 $x$ 点伤害时，发生如下情况：如果 $x < a_{\mathit{cur}}$，则从 $a_{\mathit{cur}}$ 中减去 $x$；否则，从 $h$ 中减去 $1$，并将 $a_{\mathit{cur}}$ 重新赋值为 $a$。 游戏开始时，你选择一个 $x$（一个严格大于 $0$ 的整数，可以任意大）。然后你对所有英雄进行轮流攻击：在一轮中，对所有存活的英雄各造成 $x$ 点伤害。当某个英雄的生命值变为 $0$ 时，该英雄死亡。所有英雄死亡时，游戏结束。 最后一个死亡的英雄将获得等于他作为唯一存活英雄的轮数的分数。其他英雄得分为 $0$。特别地，如果最后一轮有多个英雄同时死亡，则所有英雄得分为 $0$。 对于每一个可能的 $x$（从 $1$ 到无穷大），都要进行一次游戏。每次游戏结束后分数会重置。请问每个英雄在所有游戏中获得的最大分数是多少？

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示英雄的数量。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 2 \times 10^5$），表示每个英雄的生命值。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^5$），表示每个英雄的初始护甲值。

对于每个测试用例，输出 $n$ 个整数，表示每个英雄在所有可能的 $x$ 下获得的最大分数。

在第一个测试用例中，当 $x = 1$ 时，游戏过程如下： - 所有回合开始前：英雄的 $h = [3, 1, 2]$，$a_{\mathit{cur}} = [3, 11, 5]$； - 第 $1$ 轮：每个英雄受到 $1$ 点伤害：$h$ 仍为 $[3, 1, 2]$，$a_{\mathit{cur}}$ 变为 $[2, 10, 4]$； - 第 $2$ 轮：$h = [3, 1, 2]$，$a_{\mathit{cur}} = [1, 9, 3]$； - 第 $3$ 轮：第一个英雄护甲耗尽，生命值减 $1$：$h = [2, 1, 2]$，$a_{\mathit{cur}} = [3, 8, 2]$； - ... - 第 $9$ 轮：第一个英雄死亡，生命值变为 $0$：$h = [0, 1, 1]$，$a_{\mathit{cur}} = [0, 2, 1]$； - 第 $10$ 轮：第三个英雄死亡：$h = [0, 1, 0]$，$a_{\mathit{cur}} = [0, 1, 0]$； - 第 $11$ 轮：第二个英雄死亡：$h = [0, 0, 0]$，$a_{\mathit{cur}} = [0, 0, 0]$。 第二个英雄是最后一个死亡的，并且有一轮是唯一存活的，因此他在该局游戏中获得 $1$ 分。 当 $x = 4$ 时，游戏过程如下： - 第 $1$ 轮：$h = [2, 1, 2]$，$a_{\mathit{cur}} = [3, 7, 1]$； - 第 $2$ 轮：$h = [1, 1, 1]$，$a_{\mathit{cur}} = [3, 3, 5]$； - 第 $3$ 轮：$h = [0, 0, 1]$，$a_{\mathit{cur}} = [0, 0, 1]$； - 第 $4$ 轮：$h = [0, 0, 0]$，$a_{\mathit{cur}} = [0, 0, 0]$； 第三个英雄是最后一个死亡的，并且有一轮是唯一存活的，因此他在该局游戏中获得 $1$ 分。 由 ChatGPT 4.1 翻译