题:后缀表达式-创新互联

阳后第5天,基本康复,回归正常作息。

站在用户的角度思考问题,与客户深入沟通,找到雨湖网站设计与雨湖网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、网站设计、企业官网、英文网站、手机端网站、网站推广、域名注册、虚拟空间、企业邮箱。业务覆盖雨湖地区。

1247. 后缀表达式 - AcWing题库

给定 NN 个加号、MM 个减号以及 N+M+1N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1A1,A2,···,AN+M+1,小明想知道在所有由这 NN 个加号、MM 个减号以及 N+M+1N+M+1 个整数凑出的合法的后缀表达式中,结果大的是哪一个?

请你输出这个大的结果。

例如使用 123+−123+−,则 “23+1−”“23+1−” 这个后缀表达式结果是 44,是大的。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含 N+M+1N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1A1,A2,···,AN+M+1。

输出格式

输出一个整数,代表答案。

数据范围

0≤N,M≤1050≤N,M≤105,
−109≤Ai≤109−109≤Ai≤109

输入样例:

1 1
1 2 3

输出样例:

4

这道贪心题其实我一开始的想法是这样的:n个+,m个 - ,那就用大的数作为基数,降序排序后加上前n个,减去后m个即可。可是想法还是太简单了wrong answer。看了题解以后才明白过来:根据后缀表达式的特性,显然我们可以将多个 - 变成一个 - 和多个+(将后缀表达式表示成二叉树更好理解一些,可以参考其他佬写的这篇文章二叉树应用——后缀表达式构建表达式树_赵同学的博客-博客_后缀表达式转二叉树)

题目要求求出后缀表达式的大值,因此,当m为0时,直接加和即可;m不为0时,ans = f[max] - f[min],ans += abs(f[i])即可。

#include#include
#includeusing namespace std;

typedef long long LL;

const int N = 2e5+10;
int f[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n+m;i++) scanf("%d",&f[i]);
    
    LL ans = 0;
    if(!m) {
        for(int i=0;i<=n+m;i++) ans+=f[i];
        
    } else{
        sort(f,f+n+m+1,greater());
    
        ans = f[0] - f[n+m];
        for(int i=1;i

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


标题名称:题:后缀表达式-创新互联
文章路径:http://scyanting.com/article/gjjcg.html