空调（春季每日一题 50）

Farmer John 的 $N$ 头奶牛对他们牛棚的室温非常挑剔。

有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。

Farmer John 的牛棚包含一排 $N$ 个牛栏，编号为 $1\dots N$，每个牛栏里有一头牛。

第 $i$ 头奶牛希望她的牛栏中的温度是 $p_i$，而现在她的牛栏中的温度是 $t_i$。

为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。

该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 $1$ 个单位——例如「将牛栏 $5\dots 8$ 的温度升高 $1$ 个单位」。

一组连续的牛栏最短可以仅包含一个牛栏。

请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。

输入格式
输入的第一行包含 $N$。

下一行包含 $N$ 个非负整数 $p_1\dots p_N$，用空格分隔。

最后一行包含 $N$ 个非负整数 $t_1\dots t_N$。

输出格式
输出一个整数，为 Farmer John 需要使用的最小指令数量。

数据范围
$1\le N\le 10^5$,
$0\le p_i,t_i\le 10000$

输入样例：

5
1 5 3 3 4
1 2 2 2 1

输出样例：

5

样例解释
一组最优的 Farmer John 可以使用的指令如下：

初始温度     ：1 2 2 2 1
升高牛棚 2..5：1 3 3 3 2
升高牛棚 2..5：1 4 4 4 3
升高牛棚 2..5：1 5 5 5 4
降低牛棚 3..4：1 5 4 4 4
降低牛棚 3..4：1 5 3 3 4

---

思路：

相当于将第二个数组变为第一个数组（每次只能对连续的一段区间进行 $+1$ 或者 $-1$ 操作）
可以先用第二个数组减去第一个数组对应位置数字（即它们的差）
题目对应的意思就是把这个差数组所有元素变为 $0$
然后求这个差数组的差分数组（原数组全部变为 $0$ 也就对应的差分变为 $0$）
对原数组进行一段区间的操作相当于对差分数组变两个数组元素（假如操作的是$[l,r]$区间+1，则相当于 $差分[l]+1,差分[r+1]-1$ ），差分数组变为 $0$，则需要进行 $max$(正数之和，负数绝对值之和)次操作。
假如 $su{m}_a>su{m}_b$ ，则前 $su{m}_b$次操作为将某个正数减 $1$，将某个负数加 $1$，剩下的 $su{m}_a-su{m}_b$ 次操作为对剩下的正数或负数进行 $-1/+1$ 操作，而对 $n+1$ 位置进行 $+1/-1$ 操作 $(n+1)$ 位置的元素对原数组没有影响。

#include<iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    
    
    cin >> n;
    for(int i = 0; i < n; i++ ) scanf("%d", &a[i]);
    int x;
    for(int i = 0; i < n; i++) scanf("%d", &x), a[i] -= x;
    
    for(int i = n - 1; i > 0; i--) a[i] -= a[i-1];
    
    int neg = 0, pos = 0;
    for(int i = 0; i < n; i++)
        if(a[i] > 0) pos += a[i];
        else neg -= a[i];
    
    printf("%d\n", max(neg, pos));
    
    return 0;
}