AtCoder题解｜ABC 125D Flipping Signs

题目信息 📚

【题目描述】

There are $N$ integers, $A_1, A_2, \ldots, A_N$, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer $i$ satisfying $1 \leq i \leq N-1$. Multiply both $A_i$ and $A_{i+1}$ by $-1$.

Let $B_1, B_2, \ldots, B_N$ be the integer sequence after your operations.

Find the maximum possible value of $B_1 + B_2 + \ldots + B_N$.

【输入】

Input is given from Standard Input in the following format:

$N$

$A_1, A_2, \ldots, A_N$

【输出】

Print the maximum possible value of $B_1 + B_2 + \ldots + B_N$.

【数据范围】

All values in the input are integers.

$2 \leq N \leq 10^5$
$-10^9 \leq A_i \leq 10^9$

【输入样例1】

3
-10 5 -4

【输出样例1】

If we perform the operation as follows:

Choose $1$ as $i$, which changes the sequence to $10, -5, -4$.
Choose $2$ as $i$, which changes the sequence to $10, 5, 4$.

We have $B_1 = 10, B_2 = 5, B_3 = 4$. The sum here, $B_1 + B_2 + B_3 = 10 + 5 + 4 = 19$, is the maximum possible result.

【输入样例2】

5
10 -4 -8 -11 3

【输出样例2】

【输入样例3】

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

【输出样例3】

10000000000

The output may not fit into a 32-bit integer type.

【题目来源】

https://atcoder.jp/contests/abc125/tasks/abc125_d

题目解析 🍉

【题目分析】

思维题。

需要发现的性质：

当翻转对象为一正一负时，翻转后负号数量不变，且负号位置进行传递

当翻转对象为两负时，翻转后负号数量减2，均变成正数。

题目求数组总和的最大值，所以要尽可能增加正数的数量。所以需要使负号相邻，再通过翻转消去。

因此只需统计数组中 负号出现的个数 即可。

若负号个数为偶数个，可以通过翻转使得所有负号聚集在一起，最后统一消去
- +-+-+-+-++ → ++- - - -++++
如果负号为奇数个，将数组中绝对值最小的数变成负数，其他负号配对消去

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    // 统计数组中的负号数量，以及绝对值最小值
    LL sum = 0, cnt_neg = 0, min_v = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < 0) {
            cnt_neg++;
            a[i] = -a[i];
        }
        if (a[i] < min_v) min_v = a[i];
        sum += a[i];
    }

    // 如果负号为奇数个，将数组中绝对值最小的数变成负数，其他负号配对消去
    if (cnt_neg & 1) cout << sum - 2 * min_v << endl;
    else cout << sum << endl;  // 如果负号为偶数个，可以全部消去

    return 0;
}