CF2254E Chronostasis

Yousef 有一个隐藏的数组 $a$，长度为 $n$，且全部由严格正整数构成。 通过一次操作生成了数组 $b$： - 设 $b_1 = a_1$。 - 对于每个 $2 \le i \le n$，设 $b_i = a_i - a_{i-1}$。 - 之后，将 $b$ 的所有元素完全打乱顺序。 现在给定已打乱顺序的数组 $b$，请还原出字典序最小的原数组 $a$。如果无法通过 $b$ 的任意排列还原出全为严格正整数的数组 $a$，则输出 $-1$。

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例个数。 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组的长度。 每个测试用例的第二行为 $n$ 个整数 $b_1, b_2, \dots, b_n$ （$-10^9 \le b_i \le 10^9$），表示打乱顺序的数组 $b$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个严格正整数 $a_1, a_2, \dots, a_n$（$a_i \ge 1$），即字典序最小的还原出来的原数组 $a$。如果无法还原出全为严格正整数的数组，则输出 $-1$。

在第一个测试用例中，唯一的有效数组是 $a = [5]$。 在第二个测试用例中，不存在能还原出全为严格正整数的 $a$ 数组的有效排列，因此输出 $-1$。 在第三个测试用例中，存在一种有效排列可还原出数组 $a=[1,1,3,2,6,3]$。经过计算，得到的差分序列 $[1, 0, 2, -1, 4, -3]$ 是给定乱序 $b$ 的一个排列，并且在所有可行的还原方式中，该数组字典序最小。 由 ChatGPT 5 翻译