试题 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;
}
运行结果：
