自动搬运

查看原文

来自洛谷，原作者为

	wangyishan 写不出哪怕一个音符去祭奠你

搬运于2025-08-24 22:41:26，当前版本为作者最后更新于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;
}