闲人の题解 P7522

主要是一个巧妙的思路

题目传送门

题目分析

有一堆数，然后那两个数，让一个去减另一个得到一个新数，然后放在这堆数里
求最后一个数最大。
$ 1\le n\le 3\times 10^{5} , \left |v_i \right | \le 10^{9} $

思路

首先我们看几个样例：

3
1 2 3
ans $ = $ 4

4
-4 5 -2 -3
ans $ = $ 14

8
2 0 2 1 0 4 2 3
ans $ = $ 14
可以发现第二个样例和第三个中ans的值是所有数的绝对值之和，但是第一个样例并非如次。于是我们自己造几个数据：
6
1 1 1 1 1 1
ans $ = $ 4

6
-1 1 1 1 1 1
ans $ = $ 6

同样是六个数，为什么一个负数的差别使得一个答案是4，另一个是6。

顺着这个思路我们可以对数列中的正负性分析出一下结论：
正数 $-$ 负数可以得到一个最大值。
负数 $-$ 正数可以得到一个最小值。
当且仅当数列中存在异号的数才可以把所有的负数转化成正数从而得到最大值。
如果数列中只有同号的数则（1）若全是负数，则把最大值转化成正数，使数列中存在异号情况。（2）若全是正数，则把最小值转化成负数数，使数列中存在异号情况。
如果只有一个数，输出去就完了。

那么我们的思路就出来了：

如果异号，则输出所有数绝对值之和。
如果同号，就输出所有数绝对值之和减两次最大（小）值。
如果只有一个数，输出去。

是不是超简单。

AC代码

Code：

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 1000010;

long long n, v[N];

int main(){
    cin >> n;
    long long num = 0, ans = 0, Min = 1e9 + 1, Max_ = -1e9 - 1;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        if(Max_ < v[i]) Max_ = v[i];				//记录最大值 
        if(v[i] <= 0) {
            num ++;
        }
        if(Min > v[i]) Min = v[i];					//记录最小值 
    }
    if(n == 1) {									//判断只有一个数的情况 
        cout << v[0]; return 0;
    }
    for(int i = 0; i < n; i ++)						//所有数绝对值之和
    {
         ans += abs(v[i]);
    }
   if(num != 0 && num != n){						//如果存在异号 
       cout << ans;
   }
   else {											//如果存在同号 
       if(num == 0) cout << ans - 2 * Min;			
       else cout << ans - abs(2 * Max_);
   }
    return 0;
}