【题解】后缀表达式

关于后缀表达式（逆波兰表达式）

1. 后缀表达式计算过程：不断取出数字并压入栈中，遇到操作符时取出栈顶两个数字计算，并将结果压入栈中。
2. 每个后缀表达式都对应一棵二叉树。树的叶子全部都是数字，中间的节点全部都是操作符。按照后续遍历的方式可以得到后缀表达式的计算过程。

关于贪心细节

1. 如果 m = 0，那么所有数字只能相加。
2. 如果 m > 0，那么可以通过构造后缀表达式反转负号，使得负号的数量在 1 ~ m 之间（至少有一个负号用于反转其它负号而导致其自身无法反转）。而此时如果 n > 0，也可以用同样的方式反转正号（可以将所有正号反转为负号）。第一个数前面没有操作符，所以第一个数只能加到结果中。

为什么可以改变符号的正负？

1. 例如 3 5 + 4 - 2 - ，计算结果是 3 + 5 - 4 - 2 = 2 ，而 3 5 + 4 2 - - 的结果是 3 + 5 - (4 - 2) = 6 。

贪心 c++ 639ms

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, m;
int a[N];
LL res;

int main()
{
    cin >> n >> m;
    int r = n + m;
    for (int i = 0; i <= r; ++ i) 
        cin >> a[i];
    
    sort(a, a + n + m + 1);
    
    if (m) 
    {
        res -= a[0];
        res += a[r];
        for (int i = 1; i < r; ++ i)
            res += abs(a[i]);
    }
    else 
    {
        for (int i = 0; i <= r; i ++ ) res += a[i];
    }

    cout << res << endl;
    system("pause");
    return 0;
}