$\color{aqua}{差分}$
理解的前提:
- 原数组的某一区间的加减等价于差分数组某点的加减;
- 差分数组的定义;
- 差分数组的前n项和Sn = 0;
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int b[N];//期望温度
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
//求每头奶牛与期望的差
//即b存的是差值,差值可能为正/负数
for(int i = 1; i <= n; i ++){
int x;
scanf("%d", &x);
b[i] -= x;
}
//如果从前往后写,减去的前一个数组是被更新后的数组
//n 为什么 + 1
//原数组某区间的加减等价于差分数组某点的加减
//也就是说原数组操作的区间右端点(R)加减 等价于 差分数组的R + 1这点的加减,即差分数组的大小 + 1
for(int i = n + 1; i; i --) b[i] -= b[i - 1];
int res = 0;
for(int i = 1; i <= n + 1; i ++)
//计算所有正数的和就是操作次数?
//前提:每次只能让正数和-1/负数和+1
//因为差值可能为正/负数,所以至少操作正数和次
if(b[i] > 0)
res += b[i];
/*
if(b[i] < 0)
res -= b[i];
*/
printf("%d\n", res);
return 0;
}