CFCF2171B.Yuu Koito and Minimum Absolute Sum

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

少女漫画与情歌中的语言……总是闪闪发光。我不需要词典就能明白它们的含义……但我自己却从未亲身感受过。

——小糸侑

侑正在尝试加入学生会！不幸的是，她被要求去做文书工作……灯子要她填写各种学生会文件中的空白。

给你一个部分填充的非负整数数组 $a_1, a_2, \dots, a_n$ ，其中未填写的元素用 $-1$ 表示。你想要用非负整数填补这些空白元素，使得其差分数组所有元素之和的绝对值最小。

更正式地，令 $b$ 为长度为 $n-1$ 的数组，满足对所有 $1\leq i\leq n-1$ ，都有 $b_i = a_{i+1} - a_i$ 。请在所有可能填充 $a$ 的方案中，求出 $|b_1 + b_2 + \dots + b_{n-1}|$ 的最小值。

此外，输出能够达到这个最小值的数组。如果有多种这样的数组，请输出字典序最小的那一个 $^{\text{∗}}$ 。

$^{\text{∗}}$ 对于两个长度为 $n$ 的任意数组 $c$ 和 $d$ ，当存在某个下标 $i$ （ $1 \leq i \leq n$ ），满足对于所有 $j<i$ ，都有 $c_j = d_j$ ，且 $c_i < d_i$ ，则称 $c$ 的字典序小于 $d$ 。换言之， $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$ （字典序最小的那组）。

输入输出样例

输入#1

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

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$ 。

首页