← 返回题目列表

Codeforces · 2133/B

B. 村民

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

史蒂夫和 $$$n$$$ 其他村民住在一个村庄里。不幸的是,由于祖母绿分配的争议,这些村民中没有一个与其他村民成为朋友。此外,村民 $$$i$$$ 最初有一个 脾气暴躁 $$$g_i$$$。

Steve 可以执行以下操作任意次:

  • 选择两个村民 $$$i$$$ 和 $$$j$$$ 并给他们 $$$\text{max}(g_i, g_j)$$$ 祖母绿来分享。他们的脾气都减少了 $$$\text{min}(g_i, g_j)$$$,并且他们成为了彼此的朋友(如果他们还不是的话)。

史蒂夫希望让每个村民与其他村民成为朋友(可能通过一些中间友谊);也就是说,从任何一个村民那里,你都可以沿着友谊之路到达任何其他村民。由于他不想让村庄经济过度膨胀,请计算一下他必须放弃的最少祖母绿数量才能实现这一目标。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 村民数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$g_1, g_2,\ldots, g_n$$$ ($$$1 \le g_i \le 10^9$$$) - 每个村民最初的脾气。

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

输出

对于每个测试用例,输出一个整数 - 史蒂夫必须赠送的祖母绿的最小数量才能让每个人成为朋友。

示例

输入
复制

4
2
1 2
4
2 1 5 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
3 1 4 1 5 9

输出
复制

2
7
3000000000
14

注意

在第一个测试用例中,唯一有效的操作是 $$$i = 1$$$, $$$j = 2$$$。史蒂夫给了他们 $$$\text{max}(1, 2) = 2$$$ 祖母绿,他们成为了朋友。

在第二个测试用例中,一个最佳操作顺序如下:

  • 史蒂夫选择 $$$i = 1$$$,$$$j = 3$$$。他给了村民 $$$\text{max}(2, 5) = 5$$$ 祖母绿,他们的脾气下降了 $$$\text{min}(2, 5) = 2$$$。现在大家的脾气是$$$[0, 1, 3, 2]$$$;
  • 史蒂夫选择 $$$i = 2$$$,$$$j = 4$$$。他给了村民 $$$\text{max}(1, 2) = 2$$$ 祖母绿,他们的脾气下降了 $$$\text{min}(1, 2) = 1$$$。现在大家的脾气都是$$$[0, 0, 3, 1]$$$;
  • 史蒂夫选择 $$$i = 1$$$,$$$j = 2$$$。他给了村民 $$$\text{max}(0, 0) = 0$$$ 祖母绿,他们的脾气下降了 $$$\text{min}(0, 0) = 0$$$。现在每个人的脾气都是$$$[0, 0, 3, 1]$$$。

此后,村民 $$$(1, 3)$$$、$$$(2, 4)$$$ 和 $$$(1, 2)$$$ 成为直接好友,而其他每一对村民都通过相互友谊链连接起来。可以证明,史蒂夫花费的祖母绿不能少于 $$$7$$$ 来完成此任务。