增减序列

题意：

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

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

数据范围：

思路：

我们都知道，在一段区间加上一个数，减一个数可以用差分来做，假设差分数组 ;

在a的区间加上一个数 d ,就是​;其他位置保持不变。

题目最后要让所有的数最后都相等，那么也就是差分数组全部都等于0；那么我们只需要尽可能的使差分数组整数减少，负数增加。

所以我们就可以转成统计正有多少，负数有多少，正数-1，负数+1，那么多出来我们就可以选择​操作

设p为正数的和，q为负数的和。操作数就为,即.

那么最后相等的那个数是多少呢，数等于差分的前缀和，最后多余的部分都加给了第一个或最后一个有种。

有种答案。

code：

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

const int N = 100010;

int a[N],n,m,b[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    long long  p=0,q=0;
    for(int i=n;i>=2;i--){
        a[i]=a[i]-a[i-1];
        if(a[i]>0) p+=a[i];
        else q-=a[i];
    }
    cout<<max(p,q)<<endl;
    cout<<abs(p-q)+1<<endl;
}