1 题目描述

2 题解

这道题一上来就排序，排序把大的加起来，小的减去，喜提30分，以为是送分题，实际是坑分题。

如果给的全是加号，那只能全加起来，没话说对吧，所以输入n, m时，m如果等于0(说明没有减号)，那就一个循环把输入的值全都加起来。

如果给了至少一个负号，那你就可以构造多个负号，为啥呢，因为你可以加括号，从中缀表达式（正常的，平时数学上学的表达式）转到后缀表达式会去掉括号，就是说后缀表达式没有括号。为啥可以通过括号构造多个负号呢，看下图：

说明只要有负号就可以构造1~n+m个负号对吧，因为不能把负号消失，有负号可以构造1~n+m个负号，而不是0~n+m个负号，只要有负号就至少要减去一个数。

如果你有多个负号，只有一个加号，你也可以构造多个加号，如下图：

我上面巴拉巴拉一大堆，核心意思就是，只要有一个负号，你就能通过加括号的方式，创造出1~n+m个负号，但因为至少会存在一个负号，所以至少会减去一个数，所以需要减去一个最小的数，这样可以让结果更大一点。除了减去的这个最小的数，其他的数都可以被任意构造成加法和减法，因此如果是负数，就减去这个负数，如果是正数，就加上这个正数，这样结果最大。

如果不带任何负号，那这种情况就没法构造1~n+m个负号了对吧，因为都没负号，所以直接把所有的数全都加起来就行。

3 代码

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

const int N=200010;

long long a[N];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n+m+1;i++){
		cin>>a[i];
	}
	sort(a,a+(n+m+1),greater<int>()); // 降序排序,这样能获得最小的值，也可以升序排序，不影响，只是可以学习一下用greater<int>()构造降序排序的数组
	long long s=a[0];
	if(m==0){ // 如果没有减号
		for(int i=1;i<n+m+1;i++){
			s+=a[i];
		}
	}
	else{ // 如果有一个减号，就可以构造多个减号 
		for(int i=1;i<n+m;i++){
			s+=abs(a[i]);
		}
		s-=a[n+m]; // 如果有一个减号，那么至少有一个数字被减 
	}
	cout<<s;
}