后缀表达式 - 蓝桥云课 (lanqiao.cn)

题目描述

题目分析

30分解法：要求出最大的结果就需要加的数越大，减的数越小，以此为思路简单列举即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, m, a[N], ans;
int main()
{cin >> n >> m;int len = n + m + 1;for(int i = 1; i <= len; i ++){cin >> a[i];}sort(a + 1, a + 1 + n);for(int i = len; i >= 1; i --){if(n >= 0){ans += a[i];n --;}else{ans -= a[i];}}cout << ans;return 0;
}

但我们仔细观察会发现实际上减去的数字可以为负数，所以两个减号即可以变为正数，要将情况完全考虑出来需要讨论

满分解法：

n个加号与m个减号可以构成1到n + m个减号（所以此处需要特判如果没有减号就直接将所有数相加即可），所以至少会减一个数（1减号），至少会加一个数（n + m减号），为了使结果最大我们减去最小的数，加上最大的数，中间部分实则可以全部变为正数

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N], sum;
int main()
{cin >> n >> m;for(int i = 1; i <= n + m + 1; i ++)cin >> a[i];if(!m){for(int i = 1; i <= n + m + 1; i ++){sum += a[i];}	}else{sort(a + 1, a + 1 + n + m + 1);sum += a[n + 1 + m];sum -= a[1];for(int i = 2; i <= n + m; i ++){sum += abs(a[i]);}}cout << sum;return  0;
}