[R53B]接水 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定 $n$ 个水杯（编号从 $1$ 到 $n$），其中第 $i$ 个水杯初始时装有 $a_i$ 毫升的水，其最大容量为 $b_i$ 毫升。

接下来将依次进行 $n - 1$ 次操作。第 $i$ 次操作（$1 \le i \le n - 1$）会将第 $i$ 个水杯里的水往第 $i + 1$ 个水杯里倾倒。每次倒水时，会尽可能多地倾倒，直到第 $i$ 个水杯被彻底倒空，或者第 $i + 1$ 个水杯被装满为止。整个过程中不会有水洒出。

请计算在全部操作结束之后，每个水杯最终装有多少毫升的水。

格式

输入格式

第一行包含一个整数 $n$，表示水杯的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个水杯初始时的水量。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示每个水杯的最大容量。

输出格式

输出一行 $n$ 个整数，相邻两个整数之间用一个空格隔开，第 $i$ 个整数表示经过所有操作后，第 $i$ 个水杯最终装有的水量。

样例

样例输入 #1

3
3 2 1
5 4 6

样例输出 #1

1 0 5

样例解释 #1

初始时，三个水杯的水量分别为 $3, 2, 1$。

• 第 $1$ 次操作：将第 $1$ 个杯子的水倒入第 $2$ 个杯子。第 $2$ 个杯子的剩余容量为 $4 - 2 = 2$ 毫升，因此从第 $1$ 个杯子最多只能倒出 $2$ 毫升水。操作完成后，各水杯的水量变为 $1, 4, 1$。
• 第 $2$ 次操作：将第 $2$ 个杯子的水倒入第 $3$ 个杯子。第 $3$ 个杯子的剩余容量为 $6 - 1 = 5$ 毫升，足以装下第 $2$ 个杯子中所有的水（$4$ 毫升），因此第 $2$ 个杯子被倒空。操作完成后，各水杯的水量变为 $1, 0, 5$。

最终每个杯子的水量分别为 $1, 0, 5$。

数据规模

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq a_i \leq b_i \leq 10^9$。