← 返回题目列表

Codeforces · 1721/C

C. 最小-最大数组变换

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

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,该数组按非降序排序。您决定执行以下步骤来创建数组 $$$b_1, b_2, \dots, b_n$$$:

1. 创建一个由 $$$n$$$ 任意非负整数组成的数组 $$$d$$$。
2. 对每个 $$$b_i$$$ 设置 $$$b_i = a_i + d_i$$$。
3. 按非降序对数组 $$$b$$$ 进行排序。

您将得到结果数组$$$b$$$。对于每个索引 $$$i$$$,计算您可以选择的 $$$d_i$$$ 的最小和最大可能值,以获得给定的数组 $$$b$$$。

请注意,最小(最大)$$$d_i$$$-s 彼此独立,i。 e.它们可以从不同的可能数组 $$$d$$$ 中获得。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$、$$$b$$$ 和 $$$d$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$; $$$a_i \le a_{i+1}$$$) - 数组 $$$a$$$ 按非降序排列。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \le b_{i+1}$$$) - 数组 $$$b$$$ 按非降序排列。

输入的附加限制:

- 至少有一种方法可以通过选择由非负整数组成的数组$$$d$$$来从$$$a$$$获取数组$$$b$$$;
- $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印两行。在第一行中,打印 $$$n$$$ 整数 $$$d_1^{min}, d_2^{min}, \dots, d_n^{min}$$$,其中 $$$d_i^{min}$$$ 是可以添加到 $$$a_i$$$ 的最小可能值。

其次,打印 $$$n$$$ 整数 $$$d_1^{max}, d_2^{max}, \dots, d_n^{max}$$$,其中 $$$d_i^{max}$$$ 是可以添加到 $$$a_i$$$ 的最大可能值。

所有 $$$d_i^{min}$$$ 和 $$$d_i^{max}$$$ 值彼此独立。换句话说,对于每个$$$i$$$,$$$d_i^{min}$$$只是$$$d_i$$$所有可能值中的最小值。

示例

输入 #1

4
3
2 3 5
7 11 13
1
1000
5000
4
1 2 3 4
1 2 3 4
4
10 20 30 40
22 33 33 55

输出 #1

5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15

注意

在第一个测试用例中,为了得到$$$d_1^{min} = 5$$$,我们可以选择例如$$$d = [5, 10, 6]$$$。然后$$$b$$$$$$=$$$$$$[2+5,3+10,5+6]$$$$$$=$$$$$$[7,13,11]$$$$$$=$$$$$$[7,11,13]$$$。

对于 $$$d_2^{min} = 4$$$,我们可以选择 $$$d$$$ $$$=$$$ $$$[9, 4, 8]$$$。然后$$$b$$$$$$=$$$$$$[2+9,3+4,5+8]$$$$$$=$$$$$$[11,7,13]$$$$$$=$$$$$$[7,11,13]$$$。