思路
-
前置:两数列做差,得到新数列
-
目的:将新数列变为零,就是要把这个新数列的差分数列变为零
-
操作:对于差分数列的操作,就是在要改变区域的首项上+1,改变区域尾部-1,当然先减后加也可以。(题目要求每次只能更改1个单位温度)
-
注意:对于操作的原数列的这一部分都+1,但是差分数列这中间部分是不变的,此外,完全可以把“尾部-1”的部分放到数列以外看不到的地方,也就是在原差分数列上的某个位置只有“+1”的操作
-
结果:如果+1的次数>-1的次数,那么+1时完全也可以把-1一起给做了,至于多余的部分放在n之后用不到的地方即可。反之亦然,这样,只取两种情况的最大次数即可
模拟举例:
1 5 3 3 4
1 2 2 2 1
做差:0 3 1 1 3
差分:0 3 -2 0 2
-目的-> 0 0 0 0 0
-进而-> 做差的数列也为零
1) 0 2 -1 0 2
2) 0 1 0 0 2
3) 0 0 0 0 2
-1
4) 0 0 0 0 1
-2
5) 0 0 0 0 0
-3
显然,答案就是需要的操作数,也就是正数和与负数和绝对值的最大值 max(正,abs(负))
c++代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
a[i] -= t;
}
for (int i = n - 1; i ; i--) a[i] -= a[i - 1];
int pos = 0, neg = 0;
for (int i = 0; i < n; i++)
{
if (a[i] > 0) pos += a[i];
else neg -= a[i];
}
printf("%d\n", max(pos, neg));
return 0;
}