← 返回题目列表

Codeforces · 1795/C

C. 品茶

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

一家茶叶制造商决定进行一次大规模的茶叶品鉴会。 $$$n$$$ 品尝者将品尝$$$n$$$ 种茶。茶的种类和品尝者的编号从$$$1$$$到$$$n$$$。制造商准备了 $$$a_i$$$ 毫升第 $$$i$$$ 种茶。第$$$j$$$个品尝者可以一次喝$$$b_j$$$毫升茶。

品尝将分步骤进行。在第一步中,第 $$$i$$$ 个品尝者品尝第 $$$i$$$ 种茶。第 $$$i$$$ 级品尝者喝 $$$\min(a_i, b_i)$$$ 茶(第 $$$i$$$ 类有多少可用茶,以及第 $$$i$$$ 级品尝者可以喝多少)。 $$$a_i$$$ 也会减少这个量。

然后所有品尝者都会转向前一种茶。因此,在第二步中,第 $$$i$$$ 品尝者品尝第 $$$(i-1)$$$ 种茶。第 $$$i$$$ 个品尝者喝了 $$$\min(a_{i-1}, b_i)$$$ 茶。 $$$1$$$-st 的人结束品尝。

在第三步中,第 $$$i$$$ 个品尝者品尝第 $$$(i-2)$$$ 种茶。 $$$2$$$-nd 品尝者结束品尝。这样一直持续到大家都结束品尝为止。

看一下 $$$n = 3$$$、$$$a = [10, 20, 15]$$$、$$$b = [9, 8, 6]$$$ 的品尝过程。左行显示每种茶的当前数量。右栏中显示了每个品尝者当前喝茶的总量。箭头指示当前步骤中每种茶将进入哪个品酒师。箭头上的数字是数量——该种茶的可用量和品尝者可以喝的量的最小值。

对于每个品尝者,请打印出他/她总共要喝多少毫升茶。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 茶的种类数和品尝者的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每种茶的数量。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) - 每个品尝者一次可以喝的茶量。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数 - 第 $$$i$$$ 个值应等于第 $$$i$$$ 个品尝者将喝的茶总量。

示例

输入 #1

4
3
10 20 15
9 8 6
1
5
7
4
13 8 5 4
3 4 2 1
3
1000000000 1000000000 1000000000
1 1 1000000000

输出 #1

9 9 12 
5 
3 8 6 4 
1 2 2999999997

注意

语句中描述了第一个测试用例。以下是每个步骤后每种茶的剩余量以及每个品尝者喝过的茶总量:

- $$$a = [1, 12, 9]$$$, $$$\mathit{ans} = [9, 8, 6]$$$
- $$$a = [0, 6, 9]$$$, $$$\mathit{ans} = [9, 9, 12]$$$
- $$$a = [0, 6, 9]$$$, $$$\mathit{ans} = [9, 9, 12]$$$

在第二个测试用例中,唯一的品尝者喝了 $$$\min(5, 7)$$$ 毫升唯一种类的茶。

以下是每个步骤后每种茶的剩余量以及每个品尝者在第三个测试用例中饮用的茶总量:

- $$$a = [10, 4, 3, 3]$$$, $$$\mathit{ans} = [3, 4, 2, 1]$$$;
- $$$a = [6, 2, 2, 3]$$$, $$$\mathit{ans} = [3, 8, 4, 2]$$$;
- $$$a = [4, 1, 2, 3]$$$, $$$\mathit{ans} = [3, 8, 6, 3]$$$;
- $$$a = [3, 1, 2, 3]$$$, $$$\mathit{ans} = [3, 8, 6, 4]$$$。

以下是第四个测试用例中每个步骤后每种茶的剩余量以及每个品尝者饮用的茶总量:

- $$$a = [999999999, 999999999, 0]$$$, $$$\mathit{ans} = [1, 1, 1000000000]$$$;
- $$$a = [999999998, 0, 0]$$$, $$$\mathit{ans} = [1, 2, 1999999999]$$$;
- $$$a = [0, 0, 0]$$$, $$$\mathit{ans} = [1, 2, 2999999997]$$$。