数组最终结果只由差分数组首元素决定
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
long long arr[N];
int main(){
int n;
cin>>n;
long long s1=0,s2=0;//s1统计差分数组中除首元素外正数之和,s2统计除首元素外负数之和
for(int i=0;i<n;i++){
long long m;
cin>>m;
arr[i]+=m;
arr[i+1]-=m;
if(i){
if(arr[i]>0)s1+=arr[i];
else if(arr[i]<0)s2+=-arr[i];
}
}
cout<<min(s1,s2)+abs(s1-s2)<<endl;//操作次数
cout<<abs(s1-s2)+1;
//最终结果取决于差分数组首元素的值,故最终数组结果要看差分数组首元素被修改了几次
//对于中间两两相消的情况差分数组首元素不会被修改
//对于需要通过首或尾部消去的单元素,我们可以看通过首部消去的次数,+1是表面不会通过首部消去,全都是通过尾部消去
return 0;
}