Solution:P7522(Nurture)

Argon_Cube · 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;
}