2019年蓝桥杯C/C++ B组省赛试题I：后缀表达式题解

╰半夏微凉° 2022-12-28 14:17 142阅读 0赞

### 文章目录 ###

*  题目描述
 *  初步思路
 *  算法思路
 *  解题代码

--------------------

# 题目描述 #

![题目][05bugx.png]

# 初步思路 #

写这道题首先要了解什么叫[后缀表达式][Link 1]

了解完之后，我们开始考虑这道题目。

**想法一：** 刚拿到题目，就觉得这道题似乎很简单。将所有大的正数相加，减去所有负数或者小的正数，那么就可以得到最大的结果。

但是这道题目的位置显然说明了这道题的难度

难点就在于

> **后缀表达式中其实隐含了括号的存在**

举个例子：

2 1
    
    2 3 -1 -2

如果按照**想法一**，得到的答案为：`2 + 3 - (-2) + (-1)`结果为`6`

但是还有有更优的方法：`2 + 3 - ((-2) + (-1))`结果为`8`

那么这道题瞬间就变得复杂了起来

# 算法思路 #

那么我们顺着 `2 + 3 - ((-2) + (-1))`的思路来想

考虑符号个数：

> （1）\*\*如果没有减号，全是加号：\*\*那么将所有数字加和即可
> 
> （2）\*\*如果只有一个减号：\*\*那么就构造形如`...+...+...-(...+...+...)`的形式，只需使得括号内得到的总和负的越大，或者正的越小，即可
> 
> （3）\*\*如果存在多个减号：\*\*那么就构造形如`...+...-(...+...-...-...)`的形式
> 
> 因此可以得出，**只要存在减号(m > 0)**，那么拆掉括号后，实际的减号个数至少是1个，最多是n+m个，即`1 ~ (n + m)`

那么为了得到最大的后缀表达式的值，肯定是使得实际的减号数最少，即减号为1个时。

那么只需要加上最大值`sum += a[mmax]`，再减去最小值`sum -= a[mmin]`，加上中间所有值的绝对值`sum += abs(a[i])`，就是最后的答案`sum`

参考题解[acwing题解 by BakaC1rno][acwing_ by BakaC1rno]

# 解题代码 #

//
    //  main.cpp
    //  2019lanqiao-i
    //
    //  Created by 陈洋 on 2020/10/8.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    int a[200005];
    
    int main(int argc, const char * argv[]) {
        
        int n,m;
        
        cin >> n >> m;
        
        int len = n + m + 1;
        
        for(int i = 0; i < len; i++)
            cin >> a[i];
        
        int mmax = 0, mmin = 0;
        for(int i = 1; i < len; i++){
        
            if(a[mmax] < a[i]) mmax = i;
            if(a[mmin] > a[i]) mmin = i;
        }
        
        long long sum = 0;
        
        
        if(m == 0){
        
            for(int i = 0; i < len; i++)
                sum += a[i];
        }
        else{
        
            sum += a[mmax];
            sum -= a[mmin];
            for(int i = 0; i < len; i++){
        
                if(i != mmax && i != mmin){
        
                    sum += abs(a[i]);
                }
            }
        }
        
        cout << sum << endl;
        
        return 0;
    }

[05bugx.png]: /images/20221120/cf72b0df65b64d18b968d55f766d3dd8.png
[Link 1]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437?fromtitle=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F&fromid=6160580&fr=aladdin
[acwing_ by BakaC1rno]: https://www.acwing.com/solution/content/8491/