首页 > 试题广场 >

显生之宙

[编程题]显生之宙

热度指数：912 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众数归于本初
生命就此苏生

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

输入描述:

第一行输入一个整数 ，表示数据组数。
对于每一组数据，第一行输入一个整数 ，表示初始数列中有  个数。
接下来一行，输入  个数 ，表示初始数列。

输出描述:

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

示例1

输入

输出

3
-2

说明

对于第一组数据：一种方案是令  加上 ，结果为 。
对于第二组数据：一种方案是先令其他三个数各加上 ，数列变为 ，再令其他两个数各加上 ，数列变为 ，最后令  加上 ，结果为 。

示例2

输入

1
6
-1 -2 -3 100 200 300

输出

说明

一种方案是先令其他五个数各加上 ，数列变为 ，再令其他四个数各加上 ，数列变为 ，再令其他三个数各加上 ，数列变为 ，然后三个数依次加给下一个数，得到答案。

算法知识视频讲解

Java

牛客203596504号

首先，我们要设计贪心策略：

我们的目标是最终结果最小，显然负数尽量多加几次，正数尽量只加一次。

我们发现，越先选中的数字，可加的次数越多，那我们就按升序先排个序。

排序后，我们从第1个数起，只要是负数就把它加满，一个一个往后推。
直到只剩下正数时，就要改变策略了，每个正数只加一次，就是最终结果了。

策略设计好了，但代码能这样写吗？
不能！为什么？如果这样写，复杂度就是O(n²)，太慢了！
怎么办？看视频的同学应该记得前几天老师讲过：拆贡献！

什么是拆贡献？我们要计算每个数加了多少次，就是它的贡献。

我们开始拆贡献：

假设排序过的原始数列：a₁ a₂ a₃ a₄ a₅（我们假设全是负数）
第1轮过后：a₂+a₁ a₃+a₁ a₄+a₁ a₅+a₁每个数加了a₁，计作delta₁=a₁

第2轮过后：a₃+a₁+a₂+a₁ a₄+a₁+a₂+a₁ a₅+a₁+a₂+a₁

每个数在加了a₁的基础上又加了a₁+a₂，计作delta₂=a₁*2+a₂

第3轮不再列举，因为所有数都加过前2轮的delta，这回加的第3个数也含有前两轮的delta
可以推导出：delta₃=(a₁*2+a₂)*2+a₃

这里就能看出规律：delta_i=delta_i-1*2+a_i

还记得前面的策略吗？只剩正数时停止（当然还有一种情况，就是只剩一个数了）
我们要搞清楚，这里说的正数是现在的数，而不是原数列的数，也要加delta的
由于数列排过序，所以只要遇到正数，后面就全都是正数了。

接下来就好办了，把剩下的所有数（每个数都加过delta）加起来就完了。

照着上面逻辑写代码就很简单了（就这几行，不写注释也能看懂）：

Arrays.sort(array);
long delta = 0;
int index = 0;
long ans = 0;
while (index < n - 1 && array[index] + delta < 0) {
    delta = delta * 2 + array[index++];
}
while (index < n) {
    ans += array[index++] + delta;
}
System.out.println(ans);

发表于 2026-03-13 04:31:16 回复(1)

提交观点

问题信息

难度：

1条回答 7收藏 6浏览

显生之宙

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题