100. IncDec序列（差分序列，化区间为单点）

消息
100. IncDec序列
题目
提交记录
讨论
题解
视频讲解

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

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

输入格式
第一行输入正整数n。

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

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

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

数据范围
0<n≤105,
0≤ai<2147483648
输入样例：
4
1
1
2
2
输出样例：
1
2
难度： 中等
时/空限制： 1s / 64MB
总通过数： 623
总尝试数： 1296
来源： 《算法竞赛进阶指南》

思路： 进阶指南P23
区间操作中区间同加同减，只对差分数组区间第一个最后一个数产生影响，如此就化区间操作 为 单点操作 了 。
1.我们需要做的是将b2 到 bn对于的差分数变成0.
2.选出2~n的差分数，前一个数+d,后一个数-d。一正一负的情况下次操作最优。求出差分数列正数和P与负数和N，最小的数就是此操作需要的次数
3. 2操作后还有|P-N|个数没有配对，而b1为a[1]，b[n+1]=a[n]。可以和b[1]或者b[n+1]配对或者自己和自己消掉（自己-（+）d)。
这样需要|P-N|次操作
4. 步骤3后，产生|P-N|种结果（自己消掉1种，与b1或者bn+1消|P-N|种

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 7;
typedef long long ll;
ll a[maxn];

int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld",&a[i]);
    }
    ll N = 0,P = 0;
    for(int i = n;i >= 2;i--)
    {
        if(a[i] > a[i - 1])
        {
            P += a[i] - a[i - 1];
        }
        else
        {
            N += a[i - 1] - a[i];
        }
    }
    
    printf("%lld\n%lld\n",max(P,N),abs(P - N) + 1);
    return 0;
}