本文主要是介绍【算法】差分算法（空调），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
可用于求一个数组要变为另一个数组最少要改变多少次的次数
Farmer John 的 N 头奶牛对他们牛棚的室温非常挑剔。
有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。
Farmer John 的牛棚包含一排 N 个牛栏，编号为 1…N，每个牛栏里有一头牛。
第 i 头奶牛希望她的牛栏中的温度是 pi，而现在她的牛栏中的温度是 ti。
为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。
该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 11 个单位——例如「将牛栏 5…8的温度升高 1个单位」。
一组连续的牛栏最短可以仅包含一个牛栏。
请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。
输入格式
输入的第一行包含 N。
下一行包含 N个非负整数 p1…pN，用空格分隔。
最后一行包含 N个非负整数 t1…tN。
输出格式
输出一个整数，为 Farmer John 需要使用的最小指令数量。
数据范围
1≤N≤1e5
0≤pi,ti≤100000
输入样例：
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）将两个数组分别对应相减得出一个新的数组，为他们两个数组之间的差值，当这个新的数组全为0时，可满足题目要求
（2）对新的数组求差分，由差分可知对原数组一段连续区间 a[l,r] 内每个元素加 c ，可以转化为对差分数组 b 的端点(l+c,r+1-c),如下图
（3）再次转化只要将差分数组个端点的和变为0就可
差分数组正数的和+负数的和=0
所以正数和或负数和改变到0的次数就是最终答案
#include<iostream>
#include<algorithm>
#define N 100010
using namespace std;int n;
int a[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int t;for(int i=1;i<=n;i++){cin>>t;a[i]-=t;//求两数列之差}for(int i=n+1;i;i--){//倒着循环为了不影响下一个差分的结果a[i]-=a[i-1];//两数列之差的差分}int res=0;for(int i=1;i<=n+1;i++){if(a[i]>0) res+=a[i];//正数和}cout<<res;return 0;
}这篇关于【算法】差分算法（空调）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
