題目：
題解：
這道題目是很容易進坑的，
坑就在于，第一眼看上去，只有加號和減號，哦~簡單，把最小的都減掉就完事了，
然鵝這道題目的背景是后綴運算式，在將中綴運算式轉化成后綴運算式的程序中是要把括號什么的都去掉的，也就是說我們在運算的程序中，有可能通過巧妙利用括號，來尋找到更優的答案，
舉個例子：
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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/3602.html
標籤：C++