题目链接:https://www.lanqiao.cn/courses/2786/learning/?id=67814
简单回顾一下前缀、中缀、后缀表达式
前缀表达式:前缀表达式的运算符位于操作数之前。
前缀表达式计算方法:从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
前缀表达式举例:(- × + 3 4 5 6) = 29
中缀表达式:正常人类使用的算术表达方式
中缀表达式举例:((3 + 4) × 5 - 6) = 29
后缀表达式:后缀表达式与前缀表达式类似,只是运算符位于操作数之后。
后缀表达式计算方法:从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
后缀表达式举例:(3 4 + 5 × 6 -) = 29
这道题的意思是给我们几个数以及几个加减号,让我们怎么排列它们的位置可以让后缀表达式的值最大。
假设我们不考虑后缀表达式,就是正常的中缀表达式,那我们应该怎么组合呢?
首先对于题目给定的 N + M + 1 个数,先给它们排个序。
然后我们来分析一下负号的个数影响,举个例子:a1 < a2 < a3 < a4 < a5 < 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 时:
我们可以发现,对于a2到a5,只需要把它们的绝对值累加起来,而对于a1和a6我们再来单独看一下:
这样我们的结果就统一了。
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)