首页 > 试题广场 >

显生之宙

[编程题]显生之宙
众数归于本初
生命就此苏生
白垩色的王子给了你一个由 n 个数组成的数列，并告诉你，你需要执行 n-1 次如下操作：
选定一个数列中的数 x，再选择数列中的至少一个其他数，然后让这些数都加上 x，再将 x 移除出这个数列。
经 n-1 次操作过后，数列中最后只会剩下一个数。白垩色的王子希望你告诉他，最后剩下的那个数最小是多少。题目保证最后输出的答案的绝对值 \le 4\times 10^{18}。

输入描述:
第一行输入一个整数 T(1 \le T \le 10^5)，表示数据组数。
对于每一组数据，第一行输入一个整数 n(1 \le n\le\sum n \le 5 \times 10^5)，表示初始数列中有 n 个数。
接下来一行，输入 n 个数 a_1,a_2\dots a_n(-10^9 \le a_i \le 10^9)，表示初始数列。


输出描述:
对于每一组数据，输出一行一个整数，表示最后剩下的那个数的最小值。
示例1

输入

2
2
1 2
4
-1 8 -2 0

输出

3
-2

说明

对于第一组数据：一种方案是令 2 加上 1，结果为 3。
对于第二组数据：一种方案是先令其他三个数各加上 -2，数列变为 -3,6,-2，再令其他两个数各加上 -3，数列变为 3,-5，最后令 -5 加上 3，结果为 -2。
示例2

输入

1
6
-1 -2 -3 100 200 300

输出

549

说明

一种方案是先令其他五个数各加上 -3，数列变为 -4, -5,97,197,297，再令其他四个数各加上 -5，数列变为 -9,92,192,292，再令其他三个数各加上 -9，数列变为 83,183,283，然后三个数依次加给下一个数，得到答案。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 5浏览

热门推荐

相关试题

显生之宙

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号