错误思路 5/15
从大到小排,加号就加上最大的数,减号减去最小的数
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int w[N], n, m;
int main()
{
cin >> n >> m;
for (int i = 0; i < n+m+1; i++) cin >> w[i];
sort(w, w+n+m+1, greater<int>()); //从大到小排
int sum = w[0];
int i = 1, j = n+m;
while (n > 0) //加号
sum += w[i++], n--;
while (m > 0) //减号
sum -= w[j--], m--;
cout << sum;
return 0;
}
1、为什么最后能变成只有一个负号,后缀表达式本质是二叉树。多个负号可以变成一个正号。
2、当负号> 1
时,即至少有一个负号至少有一个正号,其余符号自由决定。负号给最小的那个数,变成正数。正号给最大的那个数,其余就是绝对值相加。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5 + 10; //范围是两倍!!
int w[N], n, m;
long long sum; //每个数范围 1e9 会爆int
int main()
{
cin >> n >> m;
for (int i = 0; i < n+m+1; i++) cin >> w[i];
if (!m) //都是正数,直接相加
{
for (int i = 0; i < n+m+1; i++)
sum += w[i];
}
else
{
sort(w, w+n+m+1, greater<int>()); //从大到小排
//有一个正号,一个负号,加上最大的,减去最小的,其余加上绝对值
sum += w[0] - w[n+m];
for (int i = 1; i < n+m; i++) sum += abs(w[i]);
}
cout << sum;
return 0;
}