题目描述

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

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

算法1

(差分) $O(n)$

思路

1. 先求原序列的差分序列b[N]

2. 只要b[n] (n=2....n)都为0，那么原序列a[n]中每一项都为b[1]即满足数列中的所有数都一样

3. 统计差分序列中正数和pos，负数和neg

4. 因为每次操作只能++,or –,所以最小操作次数 cnt=max(pos,neg)

最终的数列可能总数res=abs(pos-neg)+1 当pos==neg 就只有一种可能 a[n]=b[1]

当$pos!=neg$时，先通过成对操作将pos，neg中较小的一个变为0,不妨假设操作完之后 pos=0,neg=$neg^,$

接下来的操作就是产生不同序列的关键,对b[1]操作将影响整个的a[n],对b[n+1]操作对原序列将没有影响.

因此接下来我们可以这样来

一次{neg,b[n+1]–} 多次{neg,b[1]} 直到neg=0

两次{neg++,b[n+1]–}…

依次类推 总的答案数就是 res=abs(pos-neg)+1

const int N=100010;
int a[N],b[N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1]; //差分序列
    }
    long long  neg=0,pos=neg;
    for(int i=2;i<=n;i++){
        if(b[i]<0) neg-=b[i]; //统计差分序列中,负数和，因为每次操作只能++,或-- 
        else pos+=b[i];
    }
    cout<<min(neg,pos)+abs(pos-neg)<<endl;
    cout<<abs(neg-pos)+1<<endl;
    return 0;
}