自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:20:51，当前版本为作者最后更新于2020-04-21 07:25:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6446

题意简述：

给你两个长 $n$ 的数组 $p_i$，$k_i$

每一次操作可以将任意长度的区间每一个数 $\pm 1$

求把 $p_i$ 转换成 $k_i$ 的最小操作次数

我们可以想到，我们关心的是 $p_i$ 和$k_i$ 的差值

所以可以设 $a_i=p_i-k_i$

我们可以从左往右慢慢递推

假设在 $a_i$ 之前我们加上了 $l$ 排（删去就是负数）

可以发现，$l=a_{i-1}$，因为我们已经处理好了$a_{i-1}$

如果$a_i$和$a_{i-1}$的操作种类一样，那么我们直接把原来$a_{i-1}$用的操作右界限移一位覆盖$a_i$，也就是节省了$|a_{i-1}|$次操作，剩余的操作次数就是$max(0,|a_i|-|a_{i-1}|)$

否则，$a_{i-1}$的操作不能沿用，需要单独为$a_i$操作。次数为$abs(a_i)$

依次不断递推，每次将$ans$加上额外用的操作数。最终$ans$就是答案

复杂度空间$O(n)$，时间$O(n)$，达到了理论下限。

AC代码:

#include<iostream>
using namespace std;
int a[100000];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int a1;
		cin>>a1;
		a[i]=a1-a[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]>0&&a[i-1]>0)ans+=max(0,a[i]-a[i-1]);
		else if(a[i]>0&&a[i-1]<=0)ans+=a[i];
		else if(a[i]<0&&a[i-1]<0)ans+=max(0,a[i-1]-a[i]);//因为都是负数 
		else ans+=-a[i]; 
	}
	cout<<ans;
} 

这题数据是真的水