差分原理+练习

差分的原理和前缀和相似，我们先联想一下前缀和。

前缀和计算下标从0到n的和，记为sum[n+1];如果想要求出[l,r]区间的和，可以快速的通过sum[r+1]-sum[l]来得到 。

前缀和适用于需要多次获取指定连续区间和的情景

而差分即计算相邻两个元素的差，记为sub[i]=a[i]-a[i-1]（sub[0]=a[0]）。为什么要这样做呢？

如果我们对一段连续的区间的数进行同加或同减，那么区间内的sub数组是不会变化的，只有区间分界处的sub数组会发生变化

比如下面的数组：{1,2,3,4,5}

现在我们让[1,3]区间，也即2，3，4这三个数都加1，那么下面表格就更改为：

最终的效果是sub[1]+=1,sub[4]-=1;

于是有下面的结论：

对于差分数组，如果对原数组a的区间[l,r]同加c（c是个常数，也可以是负的）,差分数组sub[l]+=c;sub[r+1]-=c;

而如果我们想还原原数组，通过差分数组也很方便，即对差分数组进行累加求和：

a[i]为下标从[0,i]的差分数组sub之和。

差分数组适用于多次对连续区间进行同加同减操作的情景

以下是两道练习题：

码蹄集 (matiji.net)

本题提到可在区间[l,r]对工资进行修改，完美符合差分的要求。

以下代码可以求出题目所需的差分数组，因为本题编号从1开始，所以本代码下标也是从1开始的，请注意

int n;
cin >> n;
//a是工资数组
for (int i = 1; i <= n; i++)
	cin >> a[i];
//sub是差分数组
//计算差分
sub[1] = a[1];
for (int i = 2; i <= n; i++) {
	sub[i] = a[i] - a[i - 1];
}

现在问题是如何解决题目的问题。

以样例为例，进行分析（本题所指的差分数组不涉及sub[1]）

观察sub数组，题目提到一次操作可以使区间内的所有a都加1或减1，也即通过一次对[l,r]的操作,可以让sub[l]+=1且sub[r+1]-=1（也可能反之）

最终的目的是让所有人工资一样，即sub数组全为0（sub[1]除外）

眼神观察发现，可以操作[3,3]区间和[2,4]区间，让sub[3]+=1,sub[4]-=1;sub[2]+=1,sub[5]-=1，这样就达到sub数组全0的要求了。

实际上，一次操作能让sub数组里的一个数+1，让另一个数-1。设sub数组的所有正数和为P，负数和为-N（即绝对值为N）；至少进行P次操作，所有的正数才能都归0；至少进行N次操作，所有的负数才能都归0。而我们可以通过操作让正数-1的同时负数也+1。这样也符合所谓的最少操作次数的要求

比如sub数组里的正数总和为6，负数总和为-4，那么经过4次操作，最后正数总和为2，负数总和为0，这种情况比如：{2，2，2，3，4}这时候再操作两次，就可以让sub数组的元素归0（sub[1]除外）（实际上最后的操作让sub[1]+=1，但是sub[1]在本题无意义，它不能反应工资是否相同）

所以，最少的操作数就是max(P,N)，即正负数总和的绝对值中的最大值

以下是完整代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
int a[N], sub[N];

int main() {
	int n;
	cin >> n;
	//a是工资数组
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	//sub是差分数组
	sub[1] = a[1];//这句话也可以不要，因为在本题sub[1]用不到
	int pos = 0, neg = 0;//pos记录差分数组正数和，neg记录负数和
	for (int i = 2; i <= n; i++) {//从2开始
		sub[i] = a[i] - a[i - 1];
		if (sub[i] > 0) pos += sub[i];
		else neg += sub[i];
	}
	cout << max(pos, -neg);//取绝对值最大的那个
	return 0;
}

下一题

码蹄集 (matiji.net)

（讲解时本题下标依然从1开始，请注意）

我们观察最后一组数据：2 4，可以看到第三匹马高度减少了1.

可以根据题目意思归纳，如果输入是[a,b]，那么[a+1,b-1]区间的马匹的高度就会减一（初始值是最高的马高h）。

本题也是明显的连续对区间进行操作，刚好适合差分。

本题难度不高，下面直接给出代码：

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
//sub是差分数组
//本题可以省略高度数组
int n, h, f, sub[N] = { 0 };//差分数组先初始化为0，即默认一开始所有马的高度都是最高高度
int main()
{
    cin >> n >> h >> f;
    //根据前面讲的差分数组的原理，sub[1]=a[1]，也即初始高度
    sub[1] = h;
    for (int i = 1; i <= f; i++) {
        int a, b;
        cin >> a >> b;
        //保证a<b
        if (a == b) continue;
        if (a > b) swap(a, b);
        //根据刚刚的分析，真正修改的区间是[a+1,b-1]，对应需要修改的差分数组是sub[a+1]和sub[b](可对照开头的原理去理解)
        //注意sub[a+1]是减1，因为对整个区间的操作是高度减1，sub[b]是加1
        sub[a + 1] -= 1; sub[b] += 1;
    }
    //接下来根据差分数组还原原数组的方法，输出每匹马的高度
    //具体还原方法开头的原理也有，就是差分数组求和
    int height = 0;
    for (int i = 1; i <= n; i++) {
        //height是从1到i——[1,i]区间的差分数组之和
        //对应的就是a[i]的值
        height += sub[i];
        cout << height << endl;
    }
    return 0;
}

本文到此就结束了o(*￣▽￣*)ブ