题目描述
给定一个长度为 n 的数列 a1,a2,…,an,每次可以选择一个区间 [l,r]
,使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。`
小知识:
差分数组
假设有一个数组a[ ],我们给他的差分数组定义为b[],b[]的前缀和数组定义为c[]
那么b[i]=a[i]-a[i-1],且b[1]=a[1]
例:
a[]=1 2 3 6 4
那么b[]=1 1 1 3 -2
c[]=1 2 3 6 4
我们就会发现a[]=c[]
所以差分数组的前缀和等于原数组
沿用上面的例子
当我们选择b[1]和b[4]这个区间进行+1操作那b[]就变成了
b[]=2 1 1 3 -3
总结:当我们改变b[i]和b[j]这个区间,影响的是b[i]和b[j+1]
学了差分,接下来就是代码
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long b[N],a[N];//b[]差分数组
int main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
for(int i = 1;i <= n;i++){//求差分数组
b[i] = a[i]-a[i-1];
}
long long x = 0,y = 0;//x正值和 y负值和
for(int i = 2;i <= n;i++){
if(b[i] > 0)x += b[i];
else y -= b[i];
}
cout << min(x,y) + abs(x - y) << endl;//或max(x,y)
cout<<abs(x-y)+1;
return 0;//完结撒花!!!
}