【蓝桥杯】2019年第十届蓝桥杯CC++ B组省赛——I题 后缀表达式

题目：

题解：

这道题目是很容易进坑的。

坑就在于，第一眼看上去，只有加号和减号，哦~简单，把最小的都减掉就完事了。

然鹅这道题目的背景是后缀表达式，在将中缀表达式转化成后缀表达式的过程中是要把括号什么的都去掉的，也就是说我们在运算的过程中，有可能通过巧妙利用括号，来寻找到更优的答案。

举个例子：

0 2

3 2 1

按照错误想法的答案是3-2-1=0

然鹅，他可以这样3-（1-2）=4

先说结论：

（因为我也不知道自己能不能掰扯清楚

设ans为最终求的答案，sum为所有数的绝对值之和，maxx为所有数中的最大值，minn为所有数中的最小值。

分情况讨论：

①如果所有的数都>0，ans=sum-2*minn。

②如果所有的数都<0，则ans=sum+2*maxx。

③上述两种情况都不符合，即正负均有，则ans=sum。

以下进入瞎78乱讲：

对上面三种情况做出解释：

一、所有数都>0

则只需要A1+A2+…+Am-(minn-Am+1-…-An) = A1+A2+…+An-minn。

你会发现，只要所有数都为正数，那么只需要像上式那样构造，就能得到一个只需要损失一个最小值的答案，即ans=sum-2*minn。

二、所有数都<0

则只需要maxx-A1-A2-…-Am-（A（m+1）+A（m+2）+…+An) = -A1-A2-…-An+maxx。

你会发现，只要所有数都为负数，那么只需要像上式那样构造，就能得到一个只需要损失一个绝对值最小的答案，即ans=sum+2*maxx。因为全部都是负数，加上绝对值最小的负数损失最小，因此加上的是maxx，即最大值。

三、有正有负

则你会发现，无论你怎么样构造，你都能构造出来一种方法，使得最终答案为所有数的绝对值之和，即正数尽量都用加号，碰到没有加号的时候就用负号配合上括号即可保留正数；负数尽量都用负号，碰到没有负号的时候就用加号配合上括号即可把负数转化为相反数。

代码：

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; typedef long long ll; const ll maxn=1e6+50; ll a[maxn]; int main() { ll n,m; scanf("%lld %lld",&n,&m); ll maxx=-4e18,minn=4e18,sum=0; for(ll i=1;i<=n+m+1;i++) { scanf("%lld",&a[i]); if(a[i]>0)sum+=a[i]; else sum+=(-a[i]); maxx=max(maxx,a[i]); minn=min(minn,a[i]); } ll ans; if(maxx<0)ans=sum+maxx*2; else if(minn>0)ans=sum-minn*2; else ans=sum; printf("%lld\n",ans); }