AcWing 100. IncDec序列（差分约束性质）

题干：

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

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

思路：

设y[i]表示给定的数列x[i]相邻两项的差，即y[i]=x[i]-x[i-1]
那么问题就变成了将y数组的所有数变为0.
根据条件，每次只能是区间内[a,b]的所有数同时加+1或-1，这样会使区间端点旁的y[b+1]和y[a]发生变化，所以我们需要统计y中所有正数的和，所有负数的和。
其中大的值则为最少的操作。
则可能性为差值的绝对值加一。因为差值代表了需要额外平衡的数。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int inf= 0x3f3f3f3f;
int n;
long long x[200000],y[200000];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&x[i]);
    }
    ll a=0,b=0;
    for(int i=1;i<n;i++){
        int c=x[i]-x[i-1];
        if(c>0)
            a+=c;
        else
            b+=abs(c);
    }
    printf("%lld\n%lld\n",max(a,b),abs(a-b)+1);
    return 0;
}