后缀表达式

· · 题解

题目传送门

前置知识

后缀表达式如果不明白，可以参考这篇博客。在这里，我们做简短介绍：

后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)。例如：

四则表达式（我们生活中的算术式）：4+6\times 7-10
后缀表达式：4 6 7 \times + 10 -

思路

首先肯定考虑贪心，把所有数排序，把大数加上，小数减去，非常简单！代码如下（我这个是用优先队列的大根堆，也能达到效果，分析也在代码中）：

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
priority_queue<int,vector<int>,less<int> >pq;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n+m+1;i++)cin>>s,pq.push(s);//加入堆
    long long ans=0;
    n++;//加比减多一个
    while(n--){
        //cout<<pq.top()<<endl;调试
        ans+=pq.top();//加
        pq.pop();
    }
    while(m--){
        //cout<<pq.top()<<endl;调试
        ans-=pq.top();//减
        pq.pop();
    }
    cout<<ans;//output
    return 0;
}

自行满满的交上去，一看结果， 30 分，哭~

我们来想一下原因：后缀表达式顺序如同栈，先进先出，所以先算出的也有可能参与后面的算式，这在四则表达式中类同括号的作用。所以，最后的结果受括号影响，受减号和加号的顺序影响，举个例子就能看出：

输入：

0 4
1 2 3 4 5

而我们的输出就应该是 13 而不是 5，我们还可以发现在后缀表达式中真正会被减的数的个数可以被我们降到一（当减号都在一起时），所以我们只要牺牲一个最小的值，把其他数加起来就好啦。 详细的实现可以参考代码：

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s,maxx=-1,minn=1<<30;
long long ans=0;
int main() {
    cin>>n>>m;//input
    if(m==0) {//m==0，无最小值可牺牲的特判
        for(int i=1; i<=n+m+1; i++)cin>>s,ans+=s;//全加
        cout<<ans;
        return 0;
    }
    for(int i=1; i<=n+m+1; i++) {
        cin>>s;
        ans+=abs(s);
        maxx=max(maxx,s);
        minn=min(minn,s);//求最小值
    }
    cout<<(maxx-minn)+ans-abs(maxx)-abs(minn);//print，牺牲最小值
    return 0;
}

时间复杂度也十分优秀，连 sort 都不用了。

请读者诚信粘题解，遵守洛谷规则，另外，点个赞呗~