← 返回题目列表

Codeforces · 2171/B

B. 小糸悠和最小绝对和

中文机器翻译题面 查看原题
少女漫画和情歌里的歌词……总是闪闪发光。我不需要字典来理解它们的含义……但我从未亲自感受过它们。
— 小糸悠

悠正在尝试学生会!不幸的是,她被迫做文书工作……灯子要她填写各种学生会文件中的空白。

给定一个部分填充的非负整数数组 $$$a_1, a_2, \dots, a_n$$$,其中空白元素用 $$$-1$$$ 表示。您希望用非负整数填充空白元素,以便最小化其差异数组中元素之和的绝对值。

更正式地,令 $$$b$$$ 为长度 $$$n-1$$$ 的数组,使得对于所有 $$$1\leq i\leq n-1$$$,$$$b_i = a_{i+1} - a_i$$$。找出 $$$|b_1 + b_2 + \dots + b_{n-1}|$$$ 的最小可能值,以所有可能的方式填充 $$$a$$$ 的空白元素。

此外,输出达到该最小值的数组。如果有多个这样的数组,则输出其中一个 字典顺序最小$$$^{\text{*}}$$$。

$$$^{\text{*}}$$$对于长度为$$$n$$$的两个任意数组$$$c$$$和$$$d$$$,我们说$$$c$$$是 按字典顺序较小 比 $$$d$$$ 如果存在索引 $$$i$$$ ($$$1\leq i\leq n$$$) 使得 $$$c_j = d_j$$$ 对于所有 $$$j \lt i$$$ 和 $$$c_i \lt d_i$$$。换句话说,$$$c$$$和$$$d$$$至少在一个索引上不同,并且在它们不同的第一个索引处,$$$c_i$$$小于$$$d_i$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \dots, a_n$$$ ($$$-1\leq a_i \leq 10^6$$$)。

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

输出

对于每个测试用例,在第一行输出 $$$|b_1 + b_2 + \dots + b_{n-1}|$$$ 的最小可能值。然后,在第二行,输出 $$$n$$$ 整数,$$$a_1, a_2, \dots, a_n$$$ 的值在字典顺序最小的数组中达到这个最小值。

示例

输入
复制

6
4
2 -1 7 1
4
-1 2 4 -1
8
2 -1 1 5 11 12 1 -1
3
-1 -1 -1
3
2 5 4
2
-1 5

输出
复制

1
2 0 7 1
0
0 2 4 0
0
2 0 1 5 11 12 1 2
0
0 0 0
2
2 5 4
0
5 5

注意

在第一个示例中,我们填充数组 $$$a = [2, 0, 7, 1]$$$,这会产生差异数组 $$$b = [-2, 7, -6]$$$。

$$$b$$$ 中元素之和的绝对值为$$$1$$$。可以证明这是最小可能的。此外,可以证明这是达到该最小值的字典顺序最小的数组$$$a$$$。