首页 > 试题广场 >

显生之宙

[编程题]显生之宙

热度指数：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

输出

说明

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

算法知识视频讲解

AliLexiWalker

发表于 2026-03-13 00:43:09

这题可以把操作理解成“拿一个数当扩音器，把它的值广播给别人然后自己消失”。最优策略很直观：只要当前最小数是负的，就让它给所有剩余数都加一次（这样降得最快）；一旦最小数已经不负了，继续操作只会让结果变大，所以直接把剩下的数一路合并，答案就是当前总和。 void solve(){ int n; 展开全文

芊落土里土气土

发表于 2024-03-23 00:58:57

#include <bits/stdc++.h> using namespace std ; typedef long long int ll ; ll t , n , s , p ; int flag ; int main ( ) { cin >> t ; 展开全文

kilomatutinal

发表于 2026-03-13 15:51:32

这道题就是一个简简单单的贪心喵~简单引导一下喵如果值全是非负数的话，比如“0，2，4，5”来说，答案肯定是把所有数加起来就行了喵！只要有负数的话，比如“-2，-1，3，29，33”来说，想得到最小答案就有点绕了喵。第一步肯定是把后面所有数全部和第一个-2加一起才对喵。这样-2对答案影响最大喵！就变成展开全文

olone

发表于 2026-03-13 12:12:29

import java.util.*; public class Main{ static Scanner in = new Scanner(System.in); public static void solve(){ int n = in.nextInt(); 展开全文

BeauWill

发表于 2026-03-13 00:59:22

方法一：模拟、贪心、差分先考虑暴力，由于有区间修改，想到使用差分进行模拟。模拟的时候可以贪心地想到：若当前的最小值是负数，为了最小化最后的结果，就将后续的所有数全都加上这个负数；若当前的最小值不是负数，那么只找一个数加上，为了方便，就找第一个大于等于它的数即可。因此需要先对数组a排序展开全文

蒟蒻果冻01

发表于 2026-03-13 11:19:43

思路很简单，负数或0加到全局，正数加到最大的数，排序后从小到大依次处理。C++代码很短。注意到某些正数加了负数之后可能会变成负数或0，继续加到全局即可。 #include <bits/stdc++.h> using int64 = int64_t; using namespace std 展开全文

此在Dasein

发表于 2026-03-13 05:38:10

1. 问题分析首先，分析单次操作对数列总和的影响：操作描述：选定一个数，将其加到数列中至少一个其他数上，然后移除。数学表达：设当前选中的数为，选中的目标集合为（其中）。操作后，这些数变为。数列的总和变化量。目标：最小化最后的剩余值。由于最后只会剩下一个数，这个数展开全文

为芙宁娜献出心脏

发表于 2026-03-13 09:36:44

很简单的思路，不难看出贪心的来做，我们要从小到大排好序之后，如果有负数就让所有其他数字都加上这个数，然后继续看下一个数是否是负数如果所有数字都会变成负数，那么最后累加的结果就是我们要的答案如果不是所有数字都会变成负数，那么最后我们要将剩下的所有数字加上前面负数的总和的结果求和详细代码如下： / 展开全文