蓝桥杯：后缀表达式

后缀表达式【思维】

题目描述

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

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

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

输入描述

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

第二行包含 N+M+1 个整数 A₁,A₂,⋅⋅⋅,A_N+M+1。

其中，0≤N,M≤10⁵，−10⁹≤*A_i*≤10⁹。

输出描述

输出一个整，代表答案。

输入输出样例

示例

输入

1 1
1 2 3
1
2

输出

4
1

思路：

后缀表达式不同于我们常见的表达式，我们常见的表达式叫中缀表达式，如 2+3，而后缀表达式是 23+
后缀表达式是电脑喜欢的一种计算方式，采用压栈的方式计算，遇到数字就压进栈中，遇到计算符号就取出两个数
进行计算，所以后缀表达式相比于中缀表达式可以不借助括号就能进行中缀表达式的括号运算。如 2+3*(3+7)是
中缀表达式，而改成后缀表达式就是 2 3 3 7 + * + 。
所以本题不可用中缀表达式的方法计算，应该是用括号加上加减号进行中缀表达式计算来找最大值。
先对数按递增排序，将数组中的最大值减去最小值，如 6 - (-5)，其余的数如果和符号组成负数，放在括号的
里面，就能变成整数，如果是整数，就直接放在括号的外面，这样不管是正数还负数相加就行，只要一个最大值减
最小值就行，其余的相加。

代码：

#include
using namespace std;
int main()
{
	long long n,m,sum=0;
	int a[210000];
	scanf("%lld %lld",&n,&m);
	for(int i=0;i<n+m+1;i++)
		scanf("%d",&a[i]);
	sort(a,a+n+m+1);  //按递增排序 
	if(m==0) //判断是否有符号 
		for(int i=0;i<n+m+1;i++)
			sum+=a[i]; //没负号就全部加在一起 
	else 
	{   //有负号就将最大的值减去最小的值 
		sum=a[n+m]-a[0]; 
		for(int i=1;i<n+m;i++)
			sum+=abs(a[i]); //其余全部的数的绝对值相加 
	}
	printf("%lld",sum);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22