AcWing 1247. 后缀表达式

老师的讲课网址

https://www.acwing.com/video/736/

第二个图就已经告诉我们只要有一个减号，我们就可以组成至少含一个减号的所有组合
比如说一个减号三个加号我们可以组合成
1.-+++
2.–++
3.—+
4.----
所以代码如下

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int Inf=0x3f3f3f3f;
const int N=1e5+10;
int g[N*2];
int main()//主函数
{
    long long res=0;
    int n,m,k,mn=Inf,mx=-Inf;
    cin>>n>>m;
    k=n+m+1;
    for(int i=0;i<k;i++) cin>>g[i];
    sort(g,g+k);
    if(m==0)//没有减号全部都是加号相当于求和问题
    {
        for(int i=0;i<k;i++)
        res+=g[i];
        cout<<res;
        return 0;
    }
    //核心话：我们只要有一个减号，我们就可以组成至少含一个减号的所有组合
    res=g[k-1]-g[0];
    for(int i=1;i<k-1;i++)
    res+=fabs(g[i]);
    cout<<res;
}