题目描述
就是将原序列的连续一段全部增加或者减少1,求出变成目标序列的最小操作数
时间复杂度 $O(n)$
解题思路 (差分)
题目要求同时将一段子数组全部加上1或者减去1, 直觉上就考虑采用差分数组的思想, 将原数组每一项的原始温度减去目标温度, 得到每一项需要改变的数值, 然后求出该数组的差分数组, 目标是使得差分数组的每一项变成0, 我们的操作方式有2种:
- 选择任意两项, 一项加1, 另一项减1
- 选择任意一项 加1 或者 减1
显然, 使数组全部变为0的最少操作方案就是 差分数组中负数和与正数和的绝对值的最大值
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int w[N];
int n;
int main() {
cin >> n;
for(int i=1; i<=n; i++) cin >> w[i];
for(int i=1; i<=n; i++) {
int t; cin >> t;
w[i] -= t;
}
for(int i=n; i>1; i--) w[i] -= w[i-1];
int a = 0, b = 0;
for(int i=1; i<=n; i++) {
if(w[i] > 0) a += w[i];
else b -= w[i];
}
cout << max(a, b) << endl;
return 0;
}
怎么显然了呜呜!!你给我证明一下
看了四遍了,还是不懂
是操作那个差分数组,我们目标是将差分数组变成零。差分数组的常用操作不就是s[l] + 1, s[r + 1] - 1。这s[l], s[r]两个数就是差分数组里面的元素。然后就是判断正数和和负数和。
点了
其实很好证明(可以在草稿纸上举个例子跟着写一下捋顺思路),我们假设差分数组正数的和为A,负数和的绝对值为B,那么A和B只有三种可能,A>B,A=B或者A<B,A=B时一定是进行A或者B次操作1次数才最少。
那么A[HTML_REMOVED]B时(因为这两其实本质一样,就是A和B不相等)最少次数怎么得到呢?必然是先进行A和B中较小的那么多次操作1,然后进行两者数值之差次的操作2,这样的得到的次数一定是最少的,而这个数一定是A和B中的最大值。(在草稿纸上划划就明白了,纯打字想讲的清楚就会字多,写起来一看就懂了)
选择任意一项 加1 或者 减1(只改变一个的话 ,这个区间后面的不也加1了吗)
也就是为什么规则2是正确的呜呜呜
操作1是让一段区间内的数加1或者减1,操作2是让某个数开始到最后一个数全部加1或者减1。但是题解最后把问题转换成了求A-B数组的差分数组全变成0的操作,在这样的情况下操作1和2对应的就是差分数组一组数中一个加1一个减1,单个数加1或者减1(差分应用原理),你通过对差分数组操作后原序列一定会变成你想要样子。可能有点抽象,题解就是按照视频讲解说的,你可以看看视频讲解。
佬,还是不清楚操作二的意义在那?要使差值数组变为0,那差值数组的差分数组给某个数加1,对应差值数组的意义就在将后面都值都加上1哦,哪这个的意义在那啊
我把案例给你模拟一下,案例A-B数组是0 3 1 1 3,把它变成0 0 0 0 0也是把对应的差分数组0 3 -2 0 2变成 0 0 0 0 0,那么对差分数组进行两次操作1(左加右减),差分数组变成0 3 0 0 0,A-B变成0 3 3 3 3(因为让第三个到第四个这个区间都加了1),差分数组进行3次操作2变成0 0 0 0 0(减1),A-B也会变成0 0 0 0 0(对第2个以后所有数减3次1)。
左加右减左边数到右边数减1区间所有数都加上正数,左减右加左边数到右边数减1区间所有数都加上负数,你模拟一下就会发现只要算操作差分数组的次数就行了,因为你操作完差分数组最后得到的原序列一定是对的
意义就在于,得到最少次数的过程基本都需要操作2(抽象说法,好好理解过程就懂了)
嗷,恍如大悟,谢谢大佬 kiss kiss
楼主思路很好!初学记录一下差分更详细的解析。
1.选择任意两项, 一项加1, 另一项减1:原数组选取中间一段+1/-1
2.选择任意一项 加1 或者 减1:原数组从某个位置一直+1/-1到结束,或从开始一直+1/-1到某位置。
如果差分数组,负数和==正数和,那就全部采用规则1,操作方案数=负数和=正数和。否则,一部分采用规则1,一部分采用规则2,操作方案数=负数和或正数和大的那个。
最后一段描述的操作,不懂为啥这么做就是对的
要让原数组(差分数组的前缀和数组)都变成0,即让差分数组都变成0。因此,差分数组负数和==正数和时,采用规则1,负数+1,正数-1,即可实现差分数组都变成0。负数和!=正数和时,采用规则1,让负数和或正数和其一先变成0,再对剩下的负数和或正数和采用规则2。
懂了,谢谢
懂了,谢谢
说的最清楚的一段,谢谢大佬!!!
orz
orz
第一步一正一负抵消完成后剩下的不是正数就是负数,直接用第二步完成差分数组的归零,最少操作数就是第二步中数的绝对值
写了下自己的理解:
https://www.acwing.com/file_system/file/content/whole/index/content/11648043/
谢谢大佬
这题的难度是简单?wflbb
为什么要倒着差分呢
因为前缀和公式是s[i] = s[i-1]+a[i];那么差分应该是a[i] = s[i]=s[i-1];因为这里a数组和s数组是同一个数组,即s[i] = s[i]-s[i-1];需要用还未更新成差分的s[i-1]来更新,如果正向的话s[i-1]在s[i]之前就被更新过了,和背包倒序更新的原因一样
理解了,谢谢大佬
orz
orz
妙啊
orz
orz
orz
我靠真的妙,我一直以为是贪心做来着,刚开始还想过dp,就是没想到差分hh
差分数组完为什么要倒着构造呀?正着会出什么问题嘛?
差分数组的第i项需要用到原素组的第i-1项,但是这份代码是将元素组和差分数组合起来写的,如果正着构造,那么在算第i项之前第i-1项已经是差分数组的第i-1项了,而不是原数组的第i-1项。比较朴素的写法是把差分数组和元素组分开来写,这样就能看清了
噢噢,懂了,感谢大佬!
tql
tql
tql
tql
tql
厉害