题意
将原序列的连续一段全部增加或者减少1,求出变成目标序列的最小操作次数
分析
将原序列的连续一段全部增加或减少,我们不难想到用差分来做,原数组 a 与差分数组 b 之间的关系为 a[i] = a[i-1] + b[i]
比如将序列 1 2 2 2 1 变为序列 1 5 3 3 4
则对于每一项需要分别加上 0 3 1 1 3 ,所以这个问题就转化为了:
将 0 3 1 1 3 ,变为 0 0 0 0 0 ,要想原数组全为 0 ,则差分数组应也全都为 0;
将原数组某一段进行 +1 操作,实际上就是将差分数组中的两个点一个 +1 ,一个 -1,因此问题进一步转化为了:在差分数组中取一个点 +1, 一个点 -1,最终使得差分数组为 0
那么操作次数即为:max(差分数组中所有正数之和的绝对值, 所有负数之和的绝对值)
上述 0 3 1 1 3 序列对应的差分数组为 0 3 -2 0 2
第一次和第二次都是将 -2 和 2 一个 +1 一个 -1,差分数组变为 0 3 0 0 0
之后在差分数组的前五个值里面,只有一个 3 了,此时找不了一个 +1,一个 -1,但是我们可以到 第六个值往后找,之后三次操作都是 将 3 和 差分数组第六个值 -1(差分数组中第六个值开始往后的所有值无论怎样变化都不会影响到当前长度范围内的值)
写法一
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int a[N], b[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
int t;
cin >> t;
a[i]-=t;
}
for(int i = 1; i <= n; i++) b[i] = a[i] - a[i-1];
int zheng = 0, fu = 0;
for(int i = 1; i <= n; i++){
if(b[i]>0) zheng += b[i];
else fu -= b[i];
}
cout << max(zheng, fu);
return 0;
}
写法二
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int n;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
int t;
cin >> t;
a[i] -= t;
}
for(int i = n; i > 1; i--) a[i] -= a[i-1];
int zheng = 0, fu = 0;
for(int i = 1; i <= n; i++){
if(a[i]>0) zheng += a[i];
else fu -= a[i];
}
cout << max(zheng, fu);
return 0;
}