题目描述
给定一个长度为 nn 的数列 $a_1,a_2,…,a_n$每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
算法:差分
时间复杂度:$O(N)$
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int a[N],b[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i]-a[i-1];
}
//p是序列中差分值大于0的所有的和
//q是序列中差分小于0的所有的和
long long p=0,q=0;
for(int i=2;i<=n;i++){
if(b[i]>0)p+=b[i];
else if(b[i]<0)q-=b[i];
}
cout<<max(p,q)<<endl;
cout<<abs(p-q)+1<<endl;
return 0;
}