差分序列问题

差分序列是指在原序列基础上，计算每一项与前一项的差，组成的新序列。

b[i] = a[i]-a[i-1], i>1
b[1] =a[1];

想将原序列变为一样的数，差分序列b[2]->b[n]都变为0即可；

假设有这样一个序列
A = 2 3 3 4 4 3 3
B = 2 1 0 1 0 -1 0
我们只需将4变为3，然后把3变为2 或者2变为3.

4变3 后
B = 2 1 0 1 0 -1 0
B1 = 2 1 0 0 0 0 0
怎么变得?
4开始的第4个位置B[4]-1, 到第5个位置B[5+1]+1; j为要变的最后一个字符位置。

想要改变一个区间(i,j), 则 b[i]+1，b[j]-1 或者b[i]-1,b[j+1]+1 ;

有四种情况
1. 2<=i,j<=n; 此时B型如 2 0 0 0 1 0 0 -1 0 ，第5 ，6， 7 个数是多1的只要减1即可。
2. i=1;2<=j<=n;此时B型如 2 0 0 0 1 0 0 改变 第1 ，2，3，4，加1 即可.
3. 2<=i<=n; j>n;此时B型如 2 0 0 0 1 0 0 改变 第5，6，7，减1即可。
4. i=1;j>n 。此时没什么意义，整个序列全部变化。

尽量采用第一种变换，能同时消掉B中一对正负数， 次数 = min(正数和，负数和的绝对值)；
剩余的数全是正数或者全是负数，采用第二种，第三种都可以。

所以调整多少次，我们统计差分序列种的正数和负数即可。

有多少可能呢？ 最后要看第二种和第三种的组合情况。正数是1，有两种情况，2有三种情况。负数同理，是-1，有两种情况
一共有 abs(正数和-负数和的绝对值)+1情况。

#include<iostream>

using namespace std;

typedef long long LL;
int a[100001];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=n;i>0;i--) a[i]=a[i]-a[i-1];  //原数组存差分序列

    //统计差分序列的正负数
    LL pos=0,neg=0; //最大值可能为2147483648*10^5 所以用long long
    for(int i=2;i<=n;i++)
    {
        if(a[i]> 0) pos = pos+a[i]; //正数的和
        else if(a[i]<0) neg = neg - a[i]; //负数和的绝对值
    }

    cout<< min(pos,neg )+abs(pos-neg)<<endl;
    cout<<abs(pos-neg)+1<<endl;
    return 0;
}