题目描述
将序列A通过区间加减一个常数c操作变成序列B
转换一下,就是将序列A-B变成0即可
关于区间加减一个常数的操作,我们容易联想到差分,差分可将区间[l,r]加减c的操作转换到差分序列上在l与r位置上加减c的操作
样例
假设A-B的差分序列:
5 4 -8 6 3 -2
算法
(差分+贪心) $O(n)$
我们已知A-B的差分序列,易知:当将A-B转化成0时,A-B的差分序列也转化成0(除n+1位置外)
所以,我们的目的变为:通过差分序列两个位置上分别加1与减1,使得差分序列变为0(除n+1位置外)
假设差分序列中所有正数和为pos,所有负数和的绝对值为|neg|,假设pos>neg,我们可通过在正数位置上减1与负数位置上加1,使得差分序列变成只包含正数
最后,再在正数位置减去1,n+1位置上加上多余的1,即可将差分序列变为0
这种操作的步骤为:max(pos,|neg|)
且容易证明,任意操作的步骤一定大于等于max(pos,|neg|)
故答案即为:max(pos,|neg|)
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int p[N],t[N];
int b[N];//差分数组
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) scanf("%d",&t[i]);
for(int i=1;i<=n;i++){
int x=p[i]-t[i];
b[i]+=x;
b[i+1]-=x;
}
int pos=0,neg=0;
for(int i=1;i<=n;i++){
if(b[i]>0) pos+=b[i];
else neg+=(-b[i]);
}
cout<<max(pos,neg);
}