题目链接:CF1038D Slime
题目大意:
有\(n\)个史莱姆,每个史莱姆都可以吃掉相邻的史莱姆,当\(x\)吃掉\(y\)的时候,\(x\)的值变为\(x-y\),求最后所剩下的史莱姆值最大是多少。
题解:
三种情况:
1. 全是正数:选最小的正数减去一个正数使其变为负数,然后一直减去其他正数直至剩下一个正数,用这个正数去减去此时的负数,获得最大的正数,其值为所有数之和减去最小的正数的两倍;
2. 全是负数:同理,最大值为所有数的绝对值之和减去最大的负数的绝对值的两倍;
3. 正负数都有:选择相邻的正负数,相减得到的结果的绝对值是两者的绝对值相加,根据情况选择需要正数还是负数,则最大值为所有数的绝对值之和。
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
ll arr[500005];
int n;
int main() {
cin >> n;
ll minn = 0x7f7f7f7f, maxn = -0x7f7f7f7f, ans = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
ans += abs(arr[i]);
minn = min(minn, arr[i]);
maxn = max(maxn, arr[i]);
}
if (n == 1)
cout << arr[0] << endl;
else if (n == 2)
cout << max(arr[0] - arr[1], arr[1] - arr[0]) << endl;
else {
if (minn > 0)
ans -= 2 * minn;
else if (maxn < 0)
ans -= 2 * abs(maxn);
cout << ans << endl;
}
return 0;
}