A16192 | Last Man Standing
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
There are $n$ heroes in a videogame. Each hero has some health value $h$ and initial armor value $a$ . Let the current value of armor be $a_{\mathit{cur}}$ , initially equal to $a$ .
When $x$ points of damage are inflicted on a hero, the following happens: if $x < a_{\mathit{cur}}$ , then $x$ gets subtracted from $a_{\mathit{cur}}$ ; otherwise, $1$ gets subtracted from $h$ and $a_{\mathit{cur}}$ gets assigned back to $a$ .
In the start of the game, you choose the value $x$ (an integer strictly greater than $0$ , arbitrarily large). Then you keep attacking all heroes in rounds: in one round, you inflict $x$ points of damage to all alive heroes. A hero dies when his health becomes $0$ . The game ends when all heroes are dead.
The last hero to die earns the number of points, equal to the number of rounds he was the only hero alive. The other heroes get $0$ points. In particular, if the last round ends with multiple heroes dying, then every hero gets $0$ points.
The game is played for every possible $x$ (from $1$ to infinity). The points are reset between the games. What's the maximum number of points each hero has had?
When $x$ points of damage are inflicted on a hero, the following happens: if $x < a_{\mathit{cur}}$ , then $x$ gets subtracted from $a_{\mathit{cur}}$ ; otherwise, $1$ gets subtracted from $h$ and $a_{\mathit{cur}}$ gets assigned back to $a$ .
In the start of the game, you choose the value $x$ (an integer strictly greater than $0$ , arbitrarily large). Then you keep attacking all heroes in rounds: in one round, you inflict $x$ points of damage to all alive heroes. A hero dies when his health becomes $0$ . The game ends when all heroes are dead.
The last hero to die earns the number of points, equal to the number of rounds he was the only hero alive. The other heroes get $0$ points. In particular, if the last round ends with multiple heroes dying, then every hero gets $0$ points.
The game is played for every possible $x$ (from $1$ to infinity). The points are reset between the games. What's the maximum number of points each hero has had?
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 10$ ) — the number of testcases.
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of heroes.
The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ( $1 \le h_i \le 2 \cdot 10^5$ ) — the health value of each hero.
The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 2 \cdot 10^5$ ) — the initial armor value of each hero.
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of heroes.
The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ( $1 \le h_i \le 2 \cdot 10^5$ ) — the health value of each hero.
The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 2 \cdot 10^5$ ) — the initial armor value of each hero.
输出格式
For each testcase, print $n$ integers — the maximum number of points each hero has had over the games played for every possible $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
In the first testcase, the game for $x = 1$ is played as follows:
- before all rounds: the heroes have $h = [3, 1, 2]$ , $a_{\mathit{cur}} = [3, 11, 5]$ ;
- round $1$ : $1$ damage is inflicted on every hero: $h$ remains $[3, 1, 2]$ , $a_{\mathit{cur}}$ becomes $[2, 10, 4]$ ;
- round $2$ : $h = [3, 1, 2]$ , $a_{\mathit{cur}} = [1, 9, 3]$ ;
- round $3$ : the first hero runs out of armor, so he loses a health point: $h = [2, 1, 2]$ , $a_{\mathit{cur}} = [3, 8, 2]$ ;
- ...
- round $9$ : the first hero dies, since his health reaches $0$ : $h = [0, 1, 1]$ , $a_{\mathit{cur}} = [0, 2, 1]$ ;
- round $10$ : the third hero dies: $h = [0, 1, 0]$ , $a_{\mathit{cur}} = [0, 1, 0]$ ;
- round $11$ : the second hero dies: $h = [0, 0, 0]$ , $a_{\mathit{cur}} = [0, 0, 0]$ .
The second hero was the last hero to die, and he was the only hero alive during one round. Thus, he gets $1$ point for that game.
The game for $x = 4$ is played as follows:
- round $1$ : $h = [2, 1, 2]$ , $a_{\mathit{cur}} = [3, 7, 1]$ ;
- round $2$ : $h = [1, 1, 1]$ , $a_{\mathit{cur}} = [3, 3, 5]$ ;
- round $3$ : $h = [0, 0, 1]$ , $a_{\mathit{cur}} = [0, 0, 1]$ ;
- round $4$ : $h = [0, 0, 0]$ , $a_{\mathit{cur}} = [0, 0, 0]$ ;
The third hero was the last hero to die, and he was the only hero alive during one round.
- before all rounds: the heroes have $h = [3, 1, 2]$ , $a_{\mathit{cur}} = [3, 11, 5]$ ;
- round $1$ : $1$ damage is inflicted on every hero: $h$ remains $[3, 1, 2]$ , $a_{\mathit{cur}}$ becomes $[2, 10, 4]$ ;
- round $2$ : $h = [3, 1, 2]$ , $a_{\mathit{cur}} = [1, 9, 3]$ ;
- round $3$ : the first hero runs out of armor, so he loses a health point: $h = [2, 1, 2]$ , $a_{\mathit{cur}} = [3, 8, 2]$ ;
- ...
- round $9$ : the first hero dies, since his health reaches $0$ : $h = [0, 1, 1]$ , $a_{\mathit{cur}} = [0, 2, 1]$ ;
- round $10$ : the third hero dies: $h = [0, 1, 0]$ , $a_{\mathit{cur}} = [0, 1, 0]$ ;
- round $11$ : the second hero dies: $h = [0, 0, 0]$ , $a_{\mathit{cur}} = [0, 0, 0]$ .
The second hero was the last hero to die, and he was the only hero alive during one round. Thus, he gets $1$ point for that game.
The game for $x = 4$ is played as follows:
- round $1$ : $h = [2, 1, 2]$ , $a_{\mathit{cur}} = [3, 7, 1]$ ;
- round $2$ : $h = [1, 1, 1]$ , $a_{\mathit{cur}} = [3, 3, 5]$ ;
- round $3$ : $h = [0, 0, 1]$ , $a_{\mathit{cur}} = [0, 0, 1]$ ;
- round $4$ : $h = [0, 0, 0]$ , $a_{\mathit{cur}} = [0, 0, 0]$ ;
The third hero was the last hero to die, and he was the only hero alive during one round.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted