摘要
Title: 1247. 后缀表达式
Tag: 后缀表达式、贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1247. 后缀表达式

• 题意

  给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
  请你输出这个最大的结果。
  例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。

• 思路

  • $m = 0$，将全部数加起来即可
  • $m > 0$，后缀表达式其实对应着二叉树的后序遍历
    • 当我们将新的数放到左子树上且新的符号为负数时，会将原有的数据全部取反。
      
    • -号可以通过 -负数转成+号，最终就是等同于最大数减去最小数，再加上剩余所有数的绝对值

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-31 10:45:20
  FilePath: \ACM\Acwing\1247.py
  LastEditTime: 2022-03-31 11:27:36
  '''
  n, m = map(int, input().split())
  
  a = list(map(int, input().split()))
  if n == m == 0:
      print(a[0])
      exit(0)
  a.sort()
  
  if m == 0:
      print(sum(a))
  else:
      ans = a[-1] - a[0]
      for i in range(1, n + m):
          if a[i] < 0:
              ans -= a[i]
          else:
              ans += a[i]
      print(ans)