第十届蓝桥杯c/c++b组 后缀表达式
第十届蓝桥杯c/c++b组 后缀表达式
刚考完第十届蓝桥杯，觉得很不满意，但考过了也没办法，算了……
还是来说说这届的第九题吧（好像是第九题，有点忘了……）
这道题的标题是后缀表达式。
题目大意说是给n个加号，m个减号，然后再给出n + m + 1个整数，然后就可以组成很多种形式的后缀表达式，求出最大的后缀表达式对应的数值。
比如给出一个加号，一个减号，再给出三个数分别为3, 5, – 1，则当后缀表达式为35+（-1）-时，其值最大，为3 + 5 – （-1）= 9；所以输出9（不知道题意是不是这样，不知道会不会是我看错了。。。。。。。。。考完试严重怀疑自己，权当题意就是如上所述吧）
思路：
一开始我的思路是暴力枚举所有后缀表达式，然后求后缀表达式的值，最后再得出最大的值。但是想了想，这样实现起来不仅有点困难，而且复杂度也挺高。
于是我换了个思路：既然我们是求最大值，那为什么一定要用后缀表达式求呢？可不可以考虑以下思路：
为了使得表达式值最大，那么在加一个数时我加上当前最大的数，在减一个数时减去当前最小的数不就可以了吗？（不知道思路对不对，仅仅是作为考完试的总结）
所以，代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int num[100005];
int main()
{
int n, m; //n个加号， m个减号
cin >> n >> m;
int count = m + n + 1; //整数个数
for(int i = 0; i < count; i++)
{
cin >> num[i];
}
sort(num, num + count);
int sum = num[count - 1];
int curr = count - 2;
for(int i = 0; i < n; i++)
{
sum += num[curr--]; //尽量加上尽可能大的数
}
curr = 0;
for(int i = 0; i < m; i++)
{
sum -= num[curr++]; //尽量减去尽可能小的数
}
cout << sum << endl;
return 0;
}
我不知道这种思路是否严谨，也不知道我上述的实现是否正确，但是，至少能过一部分样例吧（哪怕过一丢丢应该是可以的）。（也许是我脑抽，也许这道题不会像我想象中这么简单，但是现在头真的很晕，考完试就是这样）
如果有问题，欢迎提出，我要去面壁思过了。
版权声明：本文为linguosen原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。