差分基本概念

a[1],a[2],.…a[n]
b[i]=a[i]-a[i-1],b[1]=a[1]

a[i]=b[1]+b[2]+.…+b[i]
    =a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]

由此可见，原数组就是差分数组的前缀和。我们可以举个例子：

原始数组：9  3  6  2  6  8
差分数组：9 -6  3 -4  4  2

现在有一个任务，在区间$[l,r]$上加一个常数c。

我们可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。显然可得出公式：$b[l] += c,b[r + 1] -= c$ 。

例2IncDec序列

给定一个长度为 $n$ 的数列 $a1,a2,…,an$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数$n$。

接下来$n$行，每行输入一个整数，第$i+1$行的整数代表$ai$。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

$0<n≤10^5$,
$0≤ai<2147483648$

输入样例：

4
1
1
2
2

输出样例：

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$

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int num[maxn];

inline void init()
{
    int n = 0;
    cin >> n;

    for(int i = 1;i <= n;++i)
        cin >> num[i];

    for(int i = n;i > 1;--i)
        num[i] -= num[i-1];
}

inline void frond()
{
    long long 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 << abs(pos - neg) + 1;
}

int main(void)
{
    init();

    frond();

    return 0;
}