题目描述

给定一个长度为 n(n≤10^5 ) 的数列 {a_1,a_2,…,a_n}，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入

第一行一个正整数n。
接下来n行，每行一个整数，第i+1行的整数表示ai。

输出

第一行输出最少操作次数。
第二行输出最终能得到多少种结果。

样例输入

4
1
1
2
2

样例输出

1
2

提示

对于30%的数据，n<=1000, 0<=ai<1000
另有30%的数据, n<=100000, 0<=ai<1000
对于100%的数据，n<=100000，0<=ai<2147483648

思路

可以先做一个差分,得到每一个数与它前一个数的大小关系,对于结果为负数的值可以+1抬升,或对为正数的-1降低,直至一样平,因此操作次数为MAX(ABS(负数之和),正数之和)
然后考虑结果的个数,很容易想到,最终序列只有一个值,因此操作后的值取值范围在首位两数之间,因此答案为ABS(An-A1)+1

代码

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

int n,a[100005];
long long ans;
int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    long long t1=0,t2=0;
    for (int i=2;i<=n;++i){
        int tmp=a[i]-a[i-1];
        if (tmp>0) t1+=tmp;
        else t2+=-tmp;
    }
    ans=max(t1,t2);
    cout<<ans<<endl;
    cout<<abs(a[n]-a[1])+1<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/46/