后缀表达式

• 1.题目
• 2.基本思想
• 3.代码实现

1.题目

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

请你输出这个最大的结果。

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

输入格式
第一行包含两个整数 N和 M。

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,A_(N+M+1)。

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

数据范围
0≤N,M≤105,0≤N,M≤10^5,0≤N,M≤105,
−109≤Ai≤109−10^9≤Ai≤10^9−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

4

2.基本思想

贪心策略

后缀表达式不再引用括号（其实是隐式的引用括号），比如2 3 + 1 - 这个式子，就是(2+3)−1=4, 从左向右计算，不考虑括号，运算符放在两个运算对象之后。

因为符号和数字的顺序可以随便安排，那么可以考虑下面几种情况：

• 1.如果都是加号：那么直接将所有的数字全部加起来即可
• 2.如果有一个减号，那么我们可以转化为 …+…−(…+…+…) 的形式，即分为两部分，中间一个减号，因此只要出现一个减号那么就可以视为出现一个或多个减号等同的效果。
• 3.如果出现多个减号：也可以转化为…+…−(…+…−…) 的形式，也就是说你希望它是减号时你可以把它放到括号外，你希望它是加号时，你可以把它放在括号里边，因为负负得正，因此，一个减号与多个减号可以视作一种情况。
  总结一下就是：只要m>0, 那么减号的数量实际上就是1 到n+m的任何一个数字。

因此得到下列讨论结果：

• 1.如果全是加号，答案就是所有数字直接相加。
• 2. 如果存在减号：
     如果全是正数，那么至少有一个被减去，所以把最小的那个减去即可。
     如果有正有负，那么所有正数匹配正号，所有负数匹配负号，因此将它们的绝对值直接相加
     如果全是负数，那么除了维持一个最大的负数(因为负数越大它的绝对值越小)为负数之后外，其他的全部翻正。

3.代码实现

import java.util.Arrays;
import java.util.Scanner;public class Main {static Scanner sc = new Scanner(System.in);static int a[] = new int[200010];public static void main(String[] args) {int n = sc.nextInt();int m = sc.nextInt();int k = n + m + 1;for (int i = 1; i <= k; i++) a[i] = sc.nextInt();long res = 0;if (m == 0) {//没有减号for (int i = 1; i <= k; i++) res += a[i];} else {Arrays.sort(a, 1, k + 1);//从小到大排序res = a[k] - a[1];for (int i = 2; i <= k - 1; i++) res += Math.abs(a[i]);}System.out.println(res);return;}
}