题目描述
给定 N 个加号、M 个减号以及 N+M+1 个整数 $A_1,A_2,…A_{n+m+1}$,小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中,结果最大的是哪一个?
请你输出这个最大的结果。
例如使用 123+−,则 “23+1−” 这个后缀表达式结果是 4,是最大的。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N+M+1 个整数$A_1,A_2,…,A_{n+m+1}$;
输出格式
第一行包含两个整数 N 和 M。
第二行包含 N+M+1 个整数 $A_1,A_2,…,A_{n+m+1}$。
数据范围
$0<=N,M<=10^5$
$-10^9<=A_i<=10^9$
代码问题
输入的数据范围由n和m共同决定,应该是2e5级别
贪心——分类讨论
1.性质分析
(1).从符号树的角度理解表达式——前/中/后缀表达式的区别就是前序/中序/后序遍历的区别
(2).当只有加减符号时,前/后缀表达式=中缀表达式+()
(3).有m个减号
a-b-c-d-…z -> a-(b-c-..-z)=a-b+c+…+z / a-b-c-…-z=a-b-c…-z (1<=负数的个数<=m)
(4).有n个+号(且至少有一个-号)
a+b+c+d+…z -> a-(b+c+d+…+z)=a-b-c…-z(m<=负数的个数<=m+n)
2.分类讨论
(1).m=0,直接相加
(2).(2).m!=0,由于至少有一个数为负数,我们可以直接相加,其它数直接加上绝对值即可(注意long long和abs)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int arr[N];
using namespace std;
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=n+m+1;i++){
scanf("%d",&arr[i]);
}
sort(arr+1,arr+1+n+m+1);
ll ans=0;
if(m==0){
for(int i=1;i<=n+m+1;i++){
ans+=arr[i];
}
}
else{
ans=arr[n+m+1]-arr[1];
for(int i=2;i<=n+m;i++){
ans+=abs(arr[i]);
}
}
cout << ans << endl;
return 0;
}