首页 > 试题广场 >

显生之宙

[编程题]显生之宙

时间限制：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

输出

说明

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

算法知识视频讲解

C++

kilomatutinal

这道题就是一个简简单单的贪心喵~

简单引导一下喵

如果值全是非负数的话，比如“0，2，4，5”来说，答案肯定是把所有数加起来就行了喵！

只要有负数的话，比如“-2，-1，3，29，33”来说，想得到最小答案就有点绕了喵。

第一步肯定是把后面所有数全部和第一个-2加一起才对喵。这样-2对答案影响最大喵！

就变成“-3，1，27，31”.同样的还可以变成“-2，24，28”再到“22，26”.

发现又变成全是非负数形式啦！

猫猫发现了它的策略应该是从最小值开始，如果是负数就全影响后面。

如果是正数就已经全部求和了喵！

每次都改变后面的数肯定不现实喵~

所以猫猫想到可以记录下来后面一共被减了多大的数值喵!

代码思路喵～

先加起来：把所有数字加起来，得到一个初始总和 ans喵，这个值将会和结果直接相关喵！
从小到大排序：把数字从小到大排排队，这样最负的数（最小的）就会先被处理。
用一个“小本本”记录影响：定义一个变量 jian（就是“减”的意思），它记录着之前所有操作已经让后面的数字总共减少了多少。一开始 jian = 0。
遍历每个数：
- 对于当前第 i 个数，它实际的值已经被之前的操作影响过了，所以实际值 = a[i] - jian。
- 如果这个实际值是负数，说明它还能用来让总和变得更小！我们就用它去加给后面所有的数（因为负数加给别人，别人会变小，总和就会减少）。
- 加给后面多少个数呢？后面还有 n-i-1 个数，所以这次操作会让总和增加 (后面个数 - 1) * 实际值，也就是 (n-i-2) * 实际值。因为实际值是负的，所以总和会减少。
- 于是 ans 加上这个值（注意是负的，所以 ans 变小）。
- 然后更新 jian：因为后面每个数都加了这个实际值，所以它们之后要减去的总量就变大了，jian 要减去这个实际值（实际值是负的，所以 jian 变大）。
最后输出 ans，就是最小的结果啦！

注意哦！负数越早用，加给越多的数，就能让总和变得越小。而且排序后先处理最负的，效果最好喵～

看代码喵！

#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll=long long;

void solve()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;cin >> n;
    vector<ll> a(n);
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        ans+=a[i];
    }
    sort(a.begin(),a.end());

    ll jian=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]-jian<0)//如果是负数喵
        {
            if(n-i-2>0) ans+=(a[i]-jian)*(n-i-2);
            jian-=a[i]-jian;//让jian更大喵！
        }
        else break;//如果是非负数就可以直接输出求和了喵
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin >> t;
    while(t--) solve();
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于今天 15:50:03 回复(0)

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);

发表于今天 04:31:16 回复(1)

提交观点

问题信息

难度：

2条回答 6收藏 4浏览