CF2254D Silhouette

Yousef 有一个秘密数组 $a$，其中包含 $n$ 个严格正整数。 对于每个元素 $a_i$，它的影子值 $b_i$ 定义为数组 $a$ 中所有严格小于 $a_i$ 的元素之和。形式化地表示为： $$ b_i = \sum_{\substack{1 \le j \le n\\ a_j < a_i}} a_j $$ 现给定影子数组 $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$（$0 \le b_i \le 2 \times 10^{14}$），表示影子数组。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$），为满足条件的字典序最小的有效数组 $a$。如果不存在合法数组，输出 $-1$。

在第一个测试用例中，答案为 $a = [1]$。仅有一个元素，所以没有比它更小的元素，其影子值为 $0$。因此 $a = [1]$ 是有效解。由于正整数中，$1$ 是唯一允许且最小的数，故此为字典序最小解。 在第二个测试用例中，答案为 $a = [2,5,2,5,6]$： - 每个 $2$ 都没有更小元素，因此影子值为 $0$。 - 每个 $5$，严格小的元素是两个 $2$，因此影子和为 $2+2=4$。 - $6$ 的严格小元素为两个 $2$ 和两个 $5$，影子和为 $2+2+5+5=14$。 因此影子数组正好为 $b = [0,4,0,4,14]$。 在第三个测试用例中，设 $a = [3, 2, 2]$，其影子数组的计算方式如下： - $a_1 = 3$，严格小于 $3$ 的元素有两个 $2$，所以影子和为 $2 + 2 = 4$，$b_1 = 4$。 - $a_2 = 2$，没有更小元素，所以影子值为 $0$。 - $a_3 = 2$，没有更小元素，所以影子值为 $0$。 因此影子数组为 $b = [4, 0, 0]$，与输入相符。 由 ChatGPT 5 翻译