1247. 后缀表达式
这题并没有给出完整的后缀表达式,只是给出数列和存在N个加号和M个减号
所以是可以对表达式加括号的,有了这个前提就能使得减号转换成加号
比如说4个数 a,b,c,d有3个-号,写成a-(b-c-d)=a-b+c+d,即如果有m个-号,可以将m-1个-号转换成+号
为了使得该后缀表达式的值最大可以将m-1个减号都转换成加号,让数列中的最大值和最小值相减(用掉一个减号),其他的数求绝对值相加即可得到最大的答案
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n, m, a[N];
int main(){
cin>>n>>m;
for(int i=0; i<n+m+1; i++) cin>>a[i];
LL ans = 0;
if(m == 0){//全是正数
for(int i=0; i<n+m+1; i++) ans += a[i];
}else{
//即如果有m个-号,可以将m-1个-号转换成+号
sort(a,a+n+m+1);
ans = a[n+m] - a[0];
for(int i=1; i<n+m; i++)
ans += abs(a[i]);
}
cout<<ans<<endl;
return 0;
}