题意
给定一个长度为 n 的数列 a[1],a[2],…,a[n]每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行,每行输入一个整数,第i+1行的整数代表$a_i$。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤$10^5$,
0≤a[i]<2147483648
输入样例:
4
1
1
2
2
输出样例:
1
2
分析
利用差分的思想,相邻两个数相减,得到序列b,第一个为b[1]=a[1]-a[0]=a[1]-0=a[i],则最终要求就变为b从b[2]到b[n]=0。
如果是如序列中有一段为1,3,2则b中对应有2,-1的序列,优先修改3,则3-1后实际修改为b为1,0操作为其中一个元素+1,另一个-1。优先做这样的操作,最后剩下的非0为全负或全正,设neg为负数的绝对值之和,pos为正数的绝对值之和,这样的操作就有min(pos,neg),其中这些操作的选择和次序不会影响全部操作后的结果。
剩下的只需要做abs(pos-neg)次操作就可以完成了。最终结果最多有多少个,经过分析明显有abs(pos-neg)=abs(a[n]-a[1]),并且其中无论a[2]到a[n-1]中,无论里面的数有多大或多小,经过第一步的处理,其中的数都在a[1]到a[n]的区间中,所以最多有$abs(a[n]-a[1])+1=abs(pos-neg)+1$种情况。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+9;
int s[N],a[N];
int main(){
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=a[i]-a[i-1];
}
long long pos=0,neg=0;
for(int i=2;i<=n;i++){
if(s[i]>0) pos+=s[i];
else if(s[i]<0) neg-=s[i];
}
cout<<max(pos,neg)<<endl;
cout<<abs(pos-neg)+1<<endl;
return 0;
}