← 返回题目列表

Codeforces · 1614/B

B. 沙发椅和一个新项目

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

“Divan's Sofas”公司计划在坐标线上建造 $$$n + 1$$$ 不同的建筑物,以便:

- 每个建筑物的坐标是一个整数;
- 没有两座建筑物站在同一点。

令 $$$x_i$$$ 为第 $$$i$$$ 建筑物的坐标。为了从建筑物 $$$i$$$ 到达建筑物 $$$j$$$,Divan 花费 $$$|x_i - x_j|$$$ 分钟,其中 $$$|y|$$$ 是 $$$y$$$ 的绝对值。

Divan 将要建造的所有建筑物的编号可以从 $$$0$$$ 到 $$$n$$$。这位商人将住在“Divan's Sofas”的新总部$$$0$$$大楼里。在建成后的前十年里,Divan 将参观第 $$$i$$$ 号建筑 $$$a_i$$$ 次,每次步行花费 $$$2 \cdot |x_0-x_i|$$$ 分钟。

Divan 要求您选择所有 $$$n + 1$$$ 建筑物的坐标,以便在接下来的十年中商人将花费尽可能少的步行时间。

输入

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

每个案例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 除总部外,“Divan's Sofas”将要建造的建筑物数量。

第二行包含序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是对第 $$$i$$$ 号建筑物的访问次数。

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

输出

对于每个测试用例,在第一行打印数字 $$$T$$$ — Divan 步行的最短时间。

在第二行打印 $$$n + 1$$$ 整数的序列 $$$x_0, x_1, \ldots, x_n$$$,其中 $$$x_i$$$ ($$$-10^6 \le x_i \le 10^6$$$) 是第 $$$i$$$ 建筑物的选定坐标。可以证明,存在坐标不超过$$$10^6$$$的最优答案。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
3
1 2 3
5
3 8 10 6 1
5
1 1 1 1 1
1
0

输出 #1

14
2 4 1 3
78
1 -1 0 2 3 4
18
3 6 1 5 2 4
0
1 2

注意

让我们看第一个例子。

Divan 将访问第一座建筑 $$$a_1 = 1$$$ 次,第二座 $$$a_2 = 2$$$ 次,第三座 $$$a_3 = 3$$$ 次。那么最优解之一如下:

1. 总部位于$$$x_0 = 2$$$;
2. $$$x_1 = 4$$$: Divan 将花费 $$$2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$$$ 分钟步行到第一栋大楼;
3. $$$x_2 = 1$$$: Divan 将花费 $$$2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$$$ 分钟步行到第二栋大楼;
4. $$$x_3 = 3$$$: Divan 将花费 $$$2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$$$ 分钟步行到第三栋大楼。

Divan 总共将花费 $$$4 + 4 + 6 = 14$$$ 分钟。可见,不可能通过布置建筑物来使商人花费更少的时间。

其中,$$$x = [1, 3, 2, 0]$$$、$$$x = [-5, -3, -6, -4]$$$ 也是第一个示例的正确答案。