当前位置：首页 > news >正文

P8683 [蓝桥杯 2019 省 B] 后缀表达式

news 2025/3/12 16:55:10

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;
}