试题 I: 后缀表达式

试题 I: 后缀表达式

时间限制: 1.0s
内存限制: 256.0MB
本题总分：25 分
【问题描述】
给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1, A2, · · · , AN+M+1，小
明想知道在所有由这 N 个加号、M 个减号以及 N + M + 1 个整数凑出的合法的
后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。
【输入格式】
第一行包含两个整数 N 和 M。
第二行包含 N + M + 1 个整数 A1, A2, · · · , AN+M+1。
【输出格式】
输出一个整数，代表答案。
【样例输入】

1 1
1 2 3
1
2
【样例输出】

4
1
【评测用例规模与约定】
对于所有评测用例，0 ≤ N, M ≤ 100000，−109 ≤ Ai ≤ 109

题目分析：

后缀表达式与我们平常的中缀表达式不同的是，是符号位的位置不同，后缀表达式，加减乘除等在数字的后面，根据题目我们可以知道，平常情况：我们只需通过中缀表达式加括号，来把负数变为正数求出最大值即可，其中有个规律就是，最大的数减去最小的数，加上其他数的绝对值即是最大值。特殊的情况是：全是正数的情况直接相加就行了。大神的详细讲解（点击此处）

测试代码：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200005;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll a[N];
int main()
{
	int i,j,n,m,k;
	ll ans=0;
    cin>>n>>m;
	int t=n+m;
	for(i=0;i<=t;i++){
	cin>>a[i];
	}
	//全是正数的情况 （特殊情况） 
	if(m==0){
		for(i=0;i<=t;i++) ans+=a[i];			
	}
	//平常情况 
	else{
		//由大到小 
		sort(a,a+t+1,greater<int>());
		//最大的减去最小的 ,并且加上其他的绝对值 
		ans+=a[0];ans-=a[t];
		for(i=1;i<t;i++) ans+=abs(a[i]);
	}	
cout<<ans<<endl;
	return 0;
}

运行结果：