首先,看题目描述,给定 N 个加号,与 M 个减号,要你求后缀表达式最大值,实际上就是求这些符号和数字排列起来的最大值。
这题很容易让人想到贪心。但是呢,又怎么个贪心法呢?很容易看出来,我们可以先用 sort 进行这么一个排序,之后,我们对于前 N 大的数加起来,对于剩下的数就减去,于是代码大体就出来了。
你以为完了?不!错掉 7 个测试点告诉我们一定要看数据范围,在转换后缀表达式为中缀表达式时,有可能有括号!所以,按上面我们讲的那样去做就会出错。
怎么办呢?我们可以使用 abs 函数消除括号影响。
至于后缀表达式可以参考这篇文章:https://blog.csdn.net/kexuanxiu1163/article/details/90629494
这里解释下为什么用这个函数:首先,请先看完上面推的那篇文章。
之后,我们可以知道的是,在转换后缀为中缀表达式时有一个很烦问题就是有可能有括号,这意味着什么?这意味着加减乘除先后顺序可能改变,同时,题目中给定范围有可能为负数,所以,有可能原本正确的是减去 1 加上 2 去得出值,按那个做法就可能变为了减去 1 再减 2 这显然是错误的,所以就需要使用 abs 那个函数消除此类影响。
还是那个例子,你想,我现在减去了 1 之后呢又因为 2 在括号里 2 带了个负号,那这求出正确值不就直接去掉负号也就是直接求绝对值就完了吗?
所以,这就是为什么要用这个函数对这些数做这么一个处理的原因。
最后,代码:
#include<bits/stdc++.h>
using namespace std;
long long int n,m,l;
const int N=2*1e6;
long long int a[N];
long long int s=0;
int cmp(int x,int y){
return x>y;
}
int main(){
scanf("%lld%lld",&n,&m);
l=n+m+1;
for(int i=1;i<=l;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+l+1,cmp);
if(m==0){
for(int i=1;i<=l;i++){
s+=a[i];
}
}else{
s=s+a[1];
s=s-a[l];
for(int i=2;i<=l-1;i++){
s=s+abs(a[i]);
}
}
printf("%lld",s);
return 0;
}
抄是会被棕名的!
转自本人洛谷博客,原文章时间为2023-07-17 11:48:17
标签:P8683,括号,int,题解,long,后缀,减去,表达式 From: https://www.cnblogs.com/solev/p/18015163