题目描述

关系

内容

给定 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数 $A_1,A_2,···,A_{N+M+1}$，小明想知道在所有由这 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 $123+-$，则 $“23+1-”$ 这个后缀表达式结果是 $4$，是最大的。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N+M+1$ 个整数 $A_1,A_2,···,A_{N+M+1}$。

输出格式

输出一个整数，代表答案。

数据范围

$0\le N,M\le {10}^5$,
$-{10}^9\le A_i\le {10}^9$

输入样例：

1 1
1 2 3

输出样例：

4

问题分析

最初思路

主要矛盾显然是负数，我们希望，负数尽可能作为被减数。

思路分析

这道题的题眼就是我们可以任意设置括号的位置，来改变运算意义上加号和减号的数量。什么是运算意义上的减号？就是去掉所有括号后，算术表达式实际的加号减号的数量。

而减号是主要矛盾，因为减号决定原数是否进行变号。

直接上结论：

• 如果减号数量为 0（${\displaystyle m=0}$），那么结果就为所有数加起来。
• 如果减号数量 ${\displaystyle m>0}$, 那么我就可以凑出 ${\displaystyle [1,n+m]}$ 个运算意义上的减号；
  所以，如果出现了负数，那么就用负号与之配对。将负数变为正数，如果出现正数，就用加号与之配对。如果给出的数没有正数，那么就把最小的负数与加号配对。

为什么呢？因为这是后缀表达式，所以，我们可以任意的加括号。即，有如下的形式:

可以发现，当减号数量为 1 的时候，我们可以通过把加号放到括号，来让其变为运算意义上的减号。

当减号数量 ${\displaystyle m>1}$ 的时候，情况如下：

同理，当我们希望减号为加号的时候，就将其放入括号内，当我们希望减号时，就拿出括号。例如，如何凑出 ${\displaystyle n+m}$ 个减号呢？我们只需要把所有的加号移到括号内去，将所有的减号移到括号外就可以了。但要注意，括号外必须保留一个+号。否则这个表达式是不成立的。即如下形式：

上述式子的运算意义上的减号数量为 ${\displaystyle n+m}$。

执行流程设计

1. 如果 ${\displaystyle m=0}$。那么就直接输出累加和；
2. 如果 ${\displaystyle m>0}$，假设负数有 k 个：
   1. ${\displaystyle k=n+m+1}$（全部为负数），那么我们就凑出 ${\displaystyle n+m}$ 个负号（将剩余的 ${\displaystyle n+m}$ 个负数转化为正数），再将最大的负数保留符号；
   2. ${\displaystyle k<n+m+1}$（存在正数），那么我们就凑出 k 个减号与其配对；
   3. ${\displaystyle k=0}$，只凑出一个减号，即将最小的正数转化为负数；

可以发现，最终的结果可以统一表示为我们先挑选出最大值和最小值，先把最小值反转一个符号，最大值不变号。

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n, m;
int a[N * 2];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n + m + 1; i++) scanf("%d", &a[i]);
    
    
    ll res = 0;
    if (m == 0) {
        for (int i = 0; i < n + m + 1; i++) res += a[i];
    } else {
        sort(a, a + n + m + 1);
        
        res = a[n + m] - a[0];
        for (int i = 1; i < n + m; i++) res += abs(a[i]);
    }
    printf("%lld\n", res);
    return 0;
}