题：后缀表达式-创新互联

阳后第5天，基本康复，回归正常作息。

1247. 后缀表达式 - AcWing题库

给定 NN 个加号、MM 个减号以及 N+M+1N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1A1,A2,···,AN+M+1，小明想知道在所有由这 NN 个加号、MM 个减号以及 N+M+1N+M+1 个整数凑出的合法的后缀表达式中，结果大的是哪一个？

请你输出这个大的结果。

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

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含 N+M+1N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1A1,A2,···,AN+M+1。

输出格式

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

数据范围

0≤N,M≤1050≤N,M≤105,
−109≤Ai≤109−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

4

这道贪心题其实我一开始的想法是这样的：n个+，m个 - ，那就用大的数作为基数，降序排序后加上前n个，减去后m个即可。可是想法还是太简单了wrong answer。看了题解以后才明白过来：根据后缀表达式的特性，显然我们可以将多个 - 变成一个 - 和多个+（将后缀表达式表示成二叉树更好理解一些，可以参考其他佬写的这篇文章二叉树应用——后缀表达式构建表达式树_赵同学的博客-博客_后缀表达式转二叉树）

题目要求求出后缀表达式的大值，因此，当m为0时，直接加和即可；m不为0时，ans = f[max] - f[min]，ans += abs(f[i])即可。

#include#include
#includeusing namespace std;

typedef long long LL;

const int N = 2e5+10;
int f[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n+m;i++) scanf("%d",&f[i]);
    
    LL ans = 0;
    if(!m) {
        for(int i=0;i<=n+m;i++) ans+=f[i];
        
    } else{
        sort(f,f+n+m+1,greater());
    
        ans = f[0] - f[n+m];
        for(int i=1;i
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

            分享名称：题：后缀表达式-创新互联            

            URL地址：http://cqcxhl.com/article/gjjcg.html