CF1626C Monsters And Spells

Monocarp 又在玩电脑游戏了。他是一名魔法学徒，只会一个咒语。幸运的是，这个咒语可以对怪物造成伤害。 他当前所在的关卡有 $n$ 个怪物。第 $i$ 个怪物会在关卡开始后 $k_i$ 秒出现，拥有 $h_i$ 点生命值。额外的限制是，对于所有 $1 \le i \le n$，都有 $h_i \le k_i$。所有 $k_i$ 互不相同。 Monocarp 可以在关卡开始后正整数秒的时刻施放咒语：$1, 2, 3, \dots$。咒语的伤害计算方式如下：如果他在前一秒没有施放咒语，则伤害为 $1$。否则，假设前一秒的伤害为 $x$，那么他可以选择本次伤害为 $x+1$ 或 $1$。每次施放咒语会消耗等同于伤害值的法力值。法力值不会恢复。 要击杀第 $i$ 个怪物，Monocarp 必须在怪物出现的那一刻（即 $k_i$ 秒）施放一次伤害不少于 $h_i$ 的咒语。 注意，即使当前时刻没有怪物出现，Monocarp 也可以施放咒语。 所需的法力值为所有施放咒语所消耗法力值之和。请计算 Monocarp 击杀所有怪物所需的最少法力值。 可以证明，在本题的约束下总是可以击杀所有怪物。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$），表示本关卡的怪物数量。 每个测试用例的第二行包含 $n$ 个整数 $k_1 < k_2 < \dots < k_n$（$1 \le k_i \le 10^9$），表示第 $i$ 个怪物出现的秒数。所有 $k_i$ 互不相同，且按递增顺序给出。 每个测试用例的第三行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le k_i \le 10^9$），表示第 $i$ 个怪物的生命值。 所有测试用例中 $n$ 的总和不超过 $10^4$。

对于每个测试用例，输出一个整数，表示 Monocarp 击杀所有怪物所需的最少法力值。

在第一个样例中，Monocarp 可以在第 $3, 4, 5, 6$ 秒分别施放伤害为 $1, 2, 3, 4$ 的咒语。第 $6$ 秒的伤害为 $4$，确实大于等于该时刻出现的怪物的生命值。 在第二个样例中，Monocarp 可以在第 $3, 4, 5$ 秒分别施放伤害为 $1, 2, 3$ 的咒语。 在第三个样例中，Monocarp 可以在第 $4, 5, 7, 8, 9$ 秒分别施放伤害为 $1, 2, 1, 1, 2$ 的咒语。 由 ChatGPT 4.1 翻译