100. IncDec序列 【差分+贪心】

题目链接：https://www.acwing.com/problem/content/102/

先说一下差分的概念

用途：主要用于给某一区间 加一个数，或减一个数 。o(1)的时间内完成

差分，实际上就是前缀和的逆过程，  例如 已知前缀和数组 b, 那么它的差分数组 a

a1 = b1;

a2 = b2-b1;

a3 = b3-b2;

a4 = b4-b3;

.....

an= bn-bn-1;

如果把它们相加就很容易看出： a1+a2+a3+a4+...an  = bn;

----------------------------------------------------------------------------------------

此题：

1、此题说每次在某一个区间【L,R】内加一或减一，如果暴力做的话时间复杂度是o(n)的，所以我们可以先离线出a数组的差分数组b

然后 b[L]++, b[R+1]--;     这样我们就可以保证在L，R，之间的a数组每一个数都是加了1,的   然后 b[R+1]--，是使R之后的数消除这种加1的影响。

2、要使最后的数都一样，那么b数组中的b2--->bn  一定全 0

因为 b2 = a2-a1;

        b3 = a3-a2;

        ......

        bn = an-an-1;

 

如果全0 的话， a1=a2=a3=....................=an

所以我们可以用贪心的思想，来使得b中所有数变成零。  我们知道我们在做 b[L]++, b[R+1]--;操作的时候，要找两个数配对，那么 负数++，正数--，是不是就最快了。  但是最终结果可能依然不是全 0 的，因为 abs(sum(正数)) 可能 ！= abs(sum(负数))

所以，我们可以 让最后不等于0 的数全和 b1|| bn+1   来换。 

所以 ans1 = min(pos,neg)+abs(pos-neg)

        ans2 = abs(pos-neg)+1;                        ///       如果最后剩 3  ----->   (0,3)(1,2)(,2,1)(,3,0)  这4种方案来选择 b1还是 bn+1

 

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define LL long long 

using namespace std;
const int N = 100010;
LL a[N];

int main()
{
	int n;
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=n;i>1;i--)
		{
			a[i]-=a[i-1];
		}
		LL pos = 0 , neg = 0;
		for(int i=2;i<=n;i++)
		{
			if(a[i]>0) pos+= a[i];
			else neg -=a[i];
		}
		cout<<min(pos,neg)+abs(pos-neg)<<endl;
		cout<<abs(pos-neg)+1<<endl;
	}
	return 0;
}