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

wangyishan · 2023-04-03 21:29:04 · 题解

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

题意简述

link

• 给定 N 个加号、 M 个减号以及 N+M+1（下文记为 K )个整数 A_1,A_2,\cdots,A_{N+M+1}

• 求由这 N 个加号、 M 个减号以及 K 个整数凑出的合法的后缀表达式中，结果最大的是哪一个。

• 例如输入 1 2 1 2 3，则 2 3 + 1 - 这个后缀表达式结果是 4，是最大的。

（在这里我们将这 K 个整数记为 1-idx 的集合 a )

题目分析

先上 30pts 代码：

ll ans=0;
sort(a+1,a+n+m+1+1);
for(int i=1;i<=m;i++)ans-=a[i];
for(int i=m+1;i<=n+m+1;i++)ans+=a[i];
cout<<ans;

这是一个明显的贪心思路：先排序，加上 n+1 个大数，再减去 m 个小数。

但是这个贪心能够明显的举出反例：

0 4
1 2 3 4 5

答案是 13, 他会输出 -5。因为这是一个后缀表达式，转换到中缀表达式时可能会带着括号！

现在我们的首要目标就是把括号的影响忽略掉。观察上面的例子可以发现，答案 13=5-((1-2)-3)-4)=5+4+3+2-1。让我们在举几个例子看看：

• 输入为 0 2 1 2 3,输出为 5=3-(1-2)=3+2-1;
• 输入为 1 2 4 3 2 1,输出为 8=4+3-(1-2)=4+3+2-1;
• 输入为 1 2 4 3 -2 -1,输出为 10=4+3-(-2)-(-1)=4+3+1-(-2);

可以看出，

• 在 M=0 时答案为 \sum_{i=1}^K a_i，
• 而在 M>0 时答案为 \sum_{i=2}^K \lvert {a_i} \rvert-a_1（此时 a 数组已经按从小到大排序）

证明：

首先在 M=0 时答案一定为所有数的和。

在 M>0 时，想让答案最大，那么肯定要多加上大数，减去小数。先把最大的拿出来，放到首项（K-1 个符号，K 个数，那么首项一定是正的），把最小的拿出来，放到末项。此时就构成了一个这样的表达式：a_n\pm...-(a_1\pm...)。

这时其他的数就即可以放到括号外面，又可以放到括号里面。如果是正数括号里就添-,括号外就添+,负数相反。就这样，我们把所有任意个加号和减号都转变为了绝对值！虽然“牺牲”了最小的值，但是仍然换来了最大的收益。

代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll a[1000010];int n,m;
ll ans=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n+m+1;i++)
        cin>>a[i];
    sort(a+1,a+n+m+1+1);
    if(m==0)
        for(int i=1;i<=n+m+1;i++)
            ans+=a[i];
    else{
        ans=a[n+m+1]-a[1];
        for(int i=2;i<=n+m;i++)
            ans+=abs(a[i]);//abs是c++的库函数 取绝对值
    }
    cout<<ans;
    return 0;
}