P8683题解

· · 题解

首先，看题目描述，给定 N 个加号，与 M 个减号，要你求后缀表达式最大值，实际上就是求这些符号和数字排列起来的最大值。

这题很容易让人想到贪心。但是呢，又怎么个贪心法呢？很容易看出来，我们可以先用 sort 进行这么一个排序，之后，我们对于前 N 大的数加起来，对于剩下的数就减去，于是代码大体就出来了。

你以为完了？不！错掉 7 个测试点告诉我们一定要看数据范围，在转换后缀表达式为中缀表达式时，有可能有括号！所以，按上面我们讲的那样去做就会出错。

怎么办呢？我们可以使用 abs 函数消除括号影响。

至于后缀表达式可以参考这篇文章：https://blog.csdn.net/kexuanxiu1163/article/details/90629494

这里解释下为什么用这个函数：首先，请先看完上面推的那篇文章。

之后，我们可以知道的是，在转换后缀为中缀表达式时有一个很烦问题就是有可能有括号，这意味着什么？这意味着加减乘除先后顺序可能改变，同时，题目中给定范围有可能为负数，所以，有可能原本正确的是减去 1 加上 2 去得出值，按那个做法就可能变为了减去 1 再减 2 这显然是错误的，所以就需要使用 abs 那个函数消除此类影响。

还是那个例子，你想，我现在减去了 1 之后呢又因为 2 在括号里 2 带了个负号，那这求出正确值不就直接去掉负号也就是直接求绝对值就完了吗？

所以，这就是为什么要用这个函数对这些数做这么一个处理的原因。

最后，代码：

#include<bits/stdc++.h>
using namespace std;
long long int n,m,l;
const int N=2*1e6;
long long int a[N];
long long int s=0;
int cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%lld%lld",&n,&m);
    l=n+m+1;
    for(int i=1;i<=l;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+l+1,cmp);
    if(m==0){
        for(int i=1;i<=l;i++){
            s+=a[i];
        }
    }else{
        s=s+a[1];
        s=s-a[l];
        for(int i=2;i<=l-1;i++){
            s=s+abs(a[i]);
        }
    }

    printf("%lld",s);

    return 0;
}

抄是会被棕名的！