CF 1038D Slime

题目链接: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;
}
上一篇:SDU信息门户(2)——教务系统鉴权功能(一)


下一篇:洛谷 P1073 最优贸易(DFS+DP)