Description
一个序列中不断取出两个数 (A,B) 进行 (A - B)，再把 (A - B) 丢进去，最大化最后剩下的一个数。
好像是比赛原题，题还没加先来写一下这篇。
Solution
首先左右两边不是左右两只史莱姆，而是左右两边所有的。
我们显然要得出一个最大数，一个最小数，使得答案最大。
因为有正数和负数，要分类讨论 ：
先假设一个由小到大的序列 (A)。
- 全为非负数
我们可以先排序，用最小的那一只减去除最大的以外的所有数，最后再用最大的减去这个数的，即 ：
[egin{aligned}
Ans &= A_n - (A_1 - sum_{i = 2} ^ {n - 1}A_i)\&=sum_{i = 2} ^ n - A_1
end{aligned}
]
因为现在整个序列全为正数，我们要确保最大，因为大的数字对答案贡献大，不能枚举相邻两项来是答案减小，构造一个负数，来用它减去除最大的以外的全部正数，就可以得到最小的解，再用最大的数减去即可。
- 全为负数
和全为正数一样，我们可以反过来想，我们能不能用两个最大的数构造一个正数，再用这个数减去其他数，答案是肯定的，即
[egin{aligned}
Ans &= (A_n - A_{n - 1}) - sum_{i = 1} ^ {n - 2}A_i \ &= A_n - sum_{i = 1} ^ {n - 1}A_i
end{aligned}
]
证明同上。
- 数有正有负
我们发现这种情况下，我们完全可以用所有负数减去除最大值以外的所有正数，再用最大数一一减去这些负数。
假设到从 (1 cdots j) 为负数，从 (j + 1 cdots n) 为正数。
[egin{aligned}
Ans &= A_{n} - (sum_{i = 1} ^ jA_i - sum_{i = j + 1} ^ {n - 1}A_i)\&= sum_{i = j + 1} ^ nA_i - sum_{i = 1} ^ j A_i\&=sum_{i = 1} ^ n left|A_i
ight
| end{aligned}
]
实在看不懂可以自己手膜一下。
还有就是要判断一个数的情况，这种情况下只能输出原数。
Code
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int Maxk = 500010;
int a[Maxk],Ans,n,sum,tot;
inline int read()
{
int s = 0, f = 0;char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int Abs(int x) {return x > 0 ? x : -x;}
signed main()
{
n = read();
for(int i = 1;i <= n;i ++) {
a[i] = read();
sum += a[i];
tot += Abs(a[i]);
}
if(n == 1) {
cout << a[1] << endl;
return 0;
}
sort(a + 1,a + n + 1);
if(a[1] >= 0) Ans = sum - a[1] - a[1];
else if(a[n] < 0) Ans = a[n] + a[n] - sum;
else Ans = tot;
cout << Ans << endl;
return 0;
}