← 返回题目列表

Codeforces · 1879/F

F. 最后一个站着的人

中文机器翻译题面 查看原题

电子游戏中有 $$$n$$$ 个英雄。每个英雄都有一定的生命值 $$$h$$$ 和初始护甲值 $$$a$$$。令当前护甲值为$$$a_{\mathit{cur}}$$$,最初等于$$$a$$$。

当英雄受到 $$$x$$$ 点伤害时,会发生以下情况:如果 $$$x < a_{\mathit{cur}}$$$,则从 $$$a_{\mathit{cur}}$$$ 中减去 $$$x$$$;否则,$$$1$$$ 会从 $$$h$$$ 中减去,而 $$$a_{\mathit{cur}}$$$ 会被分配回 $$$a$$$。

在游戏开始时,您选择值$$$x$$$(严格大于$$$0$$$的整数,任意大)。然后你继续回合攻击所有英雄:在一轮中,你对所有活着的英雄造成 $$$x$$$ 点伤害。当英雄的生命值变为 $$$0$$$ 时,他就会死亡。当所有英雄都死后游戏结束。

最后死去的英雄获得的分数等于他是唯一活着的英雄的回合数。其他英雄获得 $$$0$$$ 积分。特别是,如果最后一轮以多名英雄死亡而结束,则每个英雄都会获得 $$$0$$$ 积分。

游戏针对所有可能的 $$$x$$$ 进行(从 $$$1$$$ 到无穷大)。积分在比赛之间重置。每个英雄的最大积分是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 英雄的数量。

第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — 每个英雄的生命值。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 每个英雄的初始护甲值。

输出

对于每个测试用例,打印 $$$n$$$ 整数 - 每个英雄在每个可能的 $$$x$$$ 所玩的游戏中获得的最大分数。

示例

输入 #1

3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10

输出 #1

1 1 1 
20000 
0 4 0 0

注意

在第一个测试用例中,$$$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$$$:第一个英雄的护甲耗尽,因此他失去了生命值:$$$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]$$$;

第三位英雄是最后死去的英雄,也是一轮中唯一活着的英雄。