蓝桥杯历届题目及解析汇总（附思路及代码）【点击此进入】
蓝桥杯，ACM算法学习【文档】【视频】大放送【点击此进入】
第九题
标题：后缀表达式（时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分）
时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分 【问题描述】 给定 N 个加号、M 个减号以及 N + M + 1 个整数 A 1 ,A 2 ,··· ,A N+M+1 ，小 明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数凑出的合法的 后缀表达式中，结果最大的是哪一个？ 请你输出这个最大的结果。 例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。 【输入格式】 第一行包含两个整数 N 和 M。 第二行包含 N + M + 1 个整数 A 1 ,A 2 ,··· ,A N+M+1 。 【输出格式】 输出一个整数，代表答案。 【样例输入】 1 1 1 2 3 【样例输出】 4 【评测用例规模与约定】 对于所有评测用例，0 ≤ N, M ≤ 100000，−10 9 ≤ A i ≤ 10 9 。
解题思路：
这题一开始有点懵，还是被后缀表达式这个概念蒙蔽了，从概念上讲，后缀表达式的意义和中缀表达式应该是一样的，想想我们熟悉的中缀表达式，我们可以自由定制数字运算的顺序，那么后缀表达式也应该有这种能力，即能随意组合运算顺序，我们知道这个概念就行。第二点是如果只有 + 、- 运算符，那么所有的数字都可以看成是相加的，-运算符可以看成负号。那么题目就可以看成有 N + M + 1 个数字进行相加，但是必须要有 M 个数字变成其本身的相反数，我们很容易想到可以把负数变成它的相反数，就成了正数，顺序应该是先将绝对值最大的负数变成正数，再是其他的数字。我们还需要讨论负数的个数和 M 的关系：1、给定的数字本身中负数的个数小于 M，这种情况下剩下绝对值最小的几个负数。2、给定的数字本身中负数的个数大于 M， 这种情况和 1 相似。3、给定的数字本身中负数的个数等于 M，这种情况全是正数，皆大欢喜。最后做加法就行了
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std
;
const int MAXN
= 200020;
int nums
[MAXN
];
bool
com(int a
, int b
) {
return abs(a
) > abs(b
);
}
int main() {
int N
, M
;
cin
>> N
>> M
;
int n
= N
+ M
+ 1;
long long res
= 0;
for (int i
= 0; i
< n
; i
++) {
scanf("%d", nums
+ i
);
}
sort(nums
, nums
+ n
, com
);
for (int i
= 0; i
< n
&& M
> 0; i
++) {
if (nums
[i
] < 0) {
nums
[i
] = -nums
[i
];
M
--;
}
}
if (M
) {
for (int i
= n
- M
; i
< n
; i
++) {
nums
[i
] = -nums
[i
];
}
}
for (int i
= 0; i
< n
; i
++) {
res
+= nums
[i
];
}
cout
<< res
<< endl
;
return 0;
}
蓝桥杯，ACM算法进阶资料大放送
