蓝桥杯--贪心3 AcWing 1247. 后缀表达式

AcWing 1247. 后缀表达式

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

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

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

输入格式

第一行包含两个整数 N 和 M。

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

输出格式

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

数据范围

0≤N,M≤105,

−109≤Ai≤109

输入样例：

1 1

1 2 3

输出样例：

4

题意：给出n个加号、m个减号及n+m个数，求能够组成的最大值

这题很有意思，题中特意提到了后缀表达式这个概念，当时在栈与队列部分做过类似题，但如果按这个思路来想的话着实没什么解法，事实上当找到一种符号组合时，因为题中只需要求出最终值即可，在一个式子成立的情况下一定会有一个后缀表达式，因此不必在意表达式如何组成

这题的关键主要在于m个减号上，例如如果常规情况下给出两个减号和abc三个数字，一般想法肯定是用最大值减去两个小值，例如

a-b-c

但事实上，在运算中存在负负得正的概念，可以使用括号来实现

a-(b-c)

在这种情况下，同样是两个负号，实现的效果即是a+c-b，在都是正数的情况下是大于a-b-c的

而在考虑括号时，可能觉得题中并没有给出括号不能使用，但实际上可以通过改变计算顺序来实现与括号同理的功能

在表达式中，可以将符号和数字抽象成一棵符号为根节点、数字为叶节点的树，通过改变结点的位置来实现部分优先计算

例如先计算出x=b-c，使用一个负号，再令a-x，使用第二个负号， 但实际运算就相当于是使用括号将b-c括上优先计算，而实现了类似使用了一个加号的现象

同理，如果将一个加号一个减号组合计算，也可以实现将加号化为减号，但要注意的是，无论如何组合，减号是不可能被完全除去的，即在公式中最少也会存在一个减号，那么当m不等于零时，减号可以取到的个数即为1~n+m

当推理到这时，即可以实现在最少使用一个减号的情况下，给每个正数一个加号，每个负数一个减号，从而实现和值得最大化，而唯一的减号则赋予给数列中的最小值，令所有值为正数实现总和最大

最后应有一个值在表达式首无符号或理解为正号，取数列中的最大值作为这个数

代码如下

import java.io.*;
import java.util.*;

public class Main {
	static Scanner tab = new Scanner(System.in);
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N = 200010;

	static int a[]=new int [N];
	
	public static void main(String[] args) throws IOException {
		int n=tab.nextInt();
		int m=tab.nextInt();
		int k=n+m+1;
		for(int i=0;i<k;i++) {
			a[i]=tab.nextInt();
		}
		long res=0;
		if(m==0) {//无负号情况
			for(int i=0;i<k;i++) {
				res+=a[i];
			}
		}
		else {
			Arrays.sort(a,0,k);
			res=a[k-1]-a[0];//初值，最大值-最小值
			for(int i=1;i<k-1;i++) {
				res+=Math.abs(a[i]);
			}
		}
		System.out.println(res);
	}
}