题目描述

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]

，使下标在这个区间内的数都加一或者都减一。

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

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

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

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

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

数据范围
0<n≤105

0≤ai<2147483648

样例

输入样例：

4
1
1
2
2

输出样例：

1
2

算法1

此题 数列a[2005]在任何[l,r]区间内所有的数加1或者减一使数列上的所有数相等，则相邻之间的差均为0，这里用到了差分，用数组d[2005]来表示相邻数差(差分序列)， 普及一下差分的定义：
a[1]=d[1],d[2]=a[2]-a[1],d[3]=a[3]-a[2],d[i]=a[i]-d[i-1]
a[2]=d[1]+a[2]
a[3]=d[1]+d[2]+d[3]
a[i]=d[1]+d[2]+d[3]+…d[i]
若在[l,r]区间内所有的数加c(此题仅仅是+1 -1)，则值需要让d[l]+=c,d[r+1]-c,其他位置的差分值不变

此题 数列a[2005]在任何[l,r]区间内所有的数加1或者减一使数列上的所有数相等，则相邻之间的差均为0(d[2]…d[n]均为0，从d[2]看即可，d[2]等于0，a[1]=a[2],d[1]=a[1)，差分列均为0了，则数列a的各元素的值均等于a[1]或者的d[1],d[1]的值有多少情况，此题就可能有多少种结果，首先让差分序列中的正数-1，负数+1，循环着+，-，直到没有的正负数对，一个为正数，一个为负数，至于为什么要是正负配对，因为我们是要这个差分序列d[2]~d[n]都要为0，所以这样负数增加，正数减少，就可以最快地到达目标为0的状态(贪心)，其中算出差分序列（d[2]–d[n]）正数总和z,负数总和的绝对值f，这样上一步只需要需要min(z,f)次，至于无法配对的正数或者负数可以与d[1]或者与d[n+1]配对，每次加一(减一)，需要abs(z-f)次，总共需要min(z,f)+abs(z-f)=max(z,f)次。

差分列均为0了，则数列a的各元素的值均等于a[1]或者的d[1]，d[1]的值有多少情况，此题就可能有多少种结果，某个正数或者负数可以通过与d[1]或者d[n+1]配对，总共配对abs(z-f)次，与d[1]可能配对 0,1,2,3…abs(z-f) 次，所以d[1]的值有abs(z-f)+1次

补充一个小小的基础: fabs的参数为double型，返回类型也是double型
abs的参数为int型，返回类型也是int型

时间复杂度

O(n)

C++ 代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int  a[100005];
int d[100005];
int main() {
int n;
cin>>n;
long long z=0,f=0;
for (int i = 1; i<= n; ++i) {
    cin>>a[i];
    d[i]=a[i]-a[i-1];//求差分序列
    if(i>1){
    if(d[i]>0){
        z+=d[i];//求差分序列中正数和(除了d[1])
    }else{
        f-=d[i];//求差分序列中负数和的绝对值(除了d[1])
    }
    }
}
cout<<max(z,f)<<endl;
cout<<abs(z-f)+1<<endl;

    return 0;
}