2019年第十届蓝桥杯 - 省赛 - C/C++大学B组 - I. 后缀表达式

2022/1/16 20:33:57

本文主要是介绍2019年第十届蓝桥杯 - 省赛 - C/C++大学B组 - I. 后缀表达式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述

题目链接:https://www.lanqiao.cn/courses/2786/learning/?id=67814

Ideas

简单回顾一下前缀、中缀、后缀表达式
前缀表达式:前缀表达式的运算符位于操作数之前。
前缀表达式计算方法:从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
前缀表达式举例:(- × + 3 4 5 6) = 29
中缀表达式:正常人类使用的算术表达方式
中缀表达式举例:((3 + 4) × 5 - 6) = 29
后缀表达式:后缀表达式与前缀表达式类似,只是运算符位于操作数之后。
后缀表达式计算方法:从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
后缀表达式举例:(3 4 + 5 × 6 -) = 29

这道题的意思是给我们几个数以及几个加减号,让我们怎么排列它们的位置可以让后缀表达式的值最大。

假设我们不考虑后缀表达式,就是正常的中缀表达式,那我们应该怎么组合呢?

首先对于题目给定的 N + M + 1 个数,先给它们排个序。

然后我们来分析一下负号的个数影响,举个例子:a1 < a2 < a3 < a4 < a5 < a6

  1. 一个"-"号:(a1 + a2 + a3) - (a4 + a5 + a6)
  2. 两个"-"号:(a1 + a2 + a3) - (a4 + a5) - a6
  3. 三个"-"号:(a1 + a2 + a3) - a4 - a5 - a6
  4. 四个"-"号:(a1 + a2) - (a4 - a3) - a5 - a6
  5. 五个"-"号:a1 - (a5 - a2) - (a4 - a3) - a6

我们可以发现一件神奇的事情,上面几个5个式子全部都是相等的,都等价于a1 + a2 + a3 - a4 - a5 - a6

所以说负号的数量 m ≥ 1 都能转换为 m = 1 的情况,那么我们其实就可以分情况讨论了,① m = 0,② m = 1。

此时,当 m ≥ 1 的时候,问题就转换成了,有 n + m + 1 个数字,我们的负号应该放在哪。

当 m = 0 时:相当于没有负号,所有的数字累加起来就OK了。

当 m ≥ 1 时,等价于 m = 1 时:

  1. 如果所有的数都是正数,那么 (a2 + a3 + a4 + a5 + a6) - (a1) 既是最大的结果
  2. 如果所有的数都是负数,那么 (a6) - (a1 + a2 + a3 + a4 + a5) 既是最大的结果,等价于 (abs(a1) + abs(a2) + abs(a3) + abs(a4) + abs(a5)) - abs(a6),跟第1种有点类似
  3. 如果有正有负,那么 (a1 + a2 + a3) - (a4 + a5 + a6),其中a1、a2、a3是正数,a4、a5、a6是负数,既是最大的结果,等价于 (a1 + a2 + a3) + abs(a4) + abs(a5) + abs(a6)

我们可以发现,对于a2到a5,只需要把它们的绝对值累加起来,而对于a1和a6我们再来单独看一下:

  1. 如果所有的数都是正数:最后的 a6 - a1 等价于 abs(a1 - a6)
  2. 如果所有的数都是负数,也是 abs(a1) - abs(a6),等价于 abs(a1 - a6)
  3. 如果有正有负:是 a1 + abs(a6),等价于 a1 - a6,肯定是正数,所以也可以加上绝对值号:abs(a1 - a6)

这样我们的结果就统一了。

Code

Python

if __name__ == '__main__':
    n, m = map(int, input().split())
    nums = list(map(int, input().split(' ')))
    if m == 0:
        print(sum(nums))
    else:
        ans = 0
        nums.sort()
        for i in range(1, n + m):
            ans += abs(nums[i])
        ans += abs(nums[0] - nums[-1])
        print(ans)


这篇关于2019年第十届蓝桥杯 - 省赛 - C/C++大学B组 - I. 后缀表达式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程