首先将原序列转化为差分数组,然后区间修改变为相同值就变为两点修改使b[2~n]=0。
首先,原题中的序列修改就等价于差分数组中一个数增加x,另一个数减少x,因此可以记录2~n中差分数组值大于零和小于零的数量p,q,这样,可以先用min(p,q)次+1,-1,之和若p或q不为令,可以进行b[1]或b[n+1]的+1/-1,所以最小操作次数为max(p,q)。
另外可以发现,为了保证操作次数最少,必须先进行min(p,q)次2~n的+1/-1,剩下的abs(p-q)可以与1或n+1进行操作,这样b[1]就有abs(p-q)+1种值(即对1进行0,1,…,n次操作,剩下的对n+1操作),而差分数组中b[1]=a[1],并且结果中所有数都等于a[1],因此最终序列的值就为abs(p,q)+1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int n;
int a[N],b[N];
int main(){
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];
}
ll p=0,q=0;
for(int i=2;i<=n;i++){
if(b[i]>0)p+=b[i];
else q-=b[i];
}
cout << max(p,q) << endl;
cout << abs(p-q)+1 << endl;
return 0;
}