← 返回题目列表

Codeforces · 1543/B

B. 自定义轨道

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

201 号高速公路是罗克波特最繁忙的街道。交通车辆给比赛带来很多障碍,尤其是当车辆数量很多时。穿过这条高速公路的轨道可以分为 $$$n$$$ 子轨道。给定一个数组 $$$a$$$,其中 $$$a_i$$$ 表示第 $$$i$$$ 子轨道中的交通车辆数量。您将轨道的不便之处定义为 $$$\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。

您可以任意(可能为零)次执行以下操作:选择一辆交通车辆并将其从当前子轨道移动到任何其他子轨道。

找出可以实现的最小不便。

输入

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

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

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

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

输出

对于每个测试用例,打印一行包含单个整数:通过应用给定操作任意(可能为零)次数可以实现的最小不便。

示例

输入 #1

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

输出 #1

0
4
21

注意

对于第一个测试用例,您可以将汽车从 $$$3$$$-rd 子轨道移动到 $$$1$$$-st 子轨道,以获得 $$$0$$$ 不便。

对于第二个测试用例,移动任何车辆都不会减少赛道的不便。