自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 22:30:41，当前版本为作者最后更新于2021-04-25 21:08:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 【题目链接】

Link:P7522

• 【解题思路】

本题是一道贪心题。

观察样例，我们发现，想让结果最大，显然要让最后两个数差最大。

所以，我们要想办法拉开最大数与最小数的差距。

显然，一个数减正数会变小，减负数会变大。那些 $0$ 对于答案是不起作用的，随便怎么处理都好。

那么，我们可以让最大的数减负数，最小的减正数，这样可以最大化数列的极差。

显然，除了最大值与最小值外，每个数都能让答案增加这个数的绝对值。

不用排序，只要三个数：最大值，最小值，所有数绝对值总和。

复杂度 $\Theta(n)$，优于目前所有题解的 $\operatorname O(n\log_2 n)$。

哦，对了，数列中只有一个数时要特判。

• 【代码实现】

#include <iostream>
#include <cmath>

using namespace std;

int main(int argc,char* argv[],char* envp[])
{
	long long minn=0x7fffffff,maxn=-minn,tmp,cnt;
	long long sum=0;
	cin>>cnt;
	if(cnt==1)//数列中只有一个数时特判
		return (cin>>tmp,cout<<tmp)&&0;
	while(cnt--)
	{
		cin>>tmp;
		sum+=abs(tmp);
		minn=min(minn,tmp);
		maxn=max(maxn,tmp);
	}
	cout<<(long long)(sum-abs(minn)-abs(maxn)+(maxn-minn));//记得要从总和里减去最大值与最小值！
	return 0;
}