[C++知识库]差分思想（2041. 干草堆）

差分是一种算法。

先看AcWing上的一道题目↓

贝茜对她最近在农场周围造成的一切恶作剧感到抱歉，她同意帮助农夫约翰把一批新到的干草捆堆起来。

开始时，共有 N 个空干草堆，编号 1～N。

约翰给贝茜下达了 K 个指令，每条指令的格式为 A B，这意味着贝茜要在 A..B范围内的每个干草堆的顶部添加一个新的干草捆。

例如，如果贝茜收到指令 10 13，则她应在干草堆 10,11,12,13中各添加一个干草捆。

在贝茜完成了所有指令后，约翰想知道 N个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度。

方便起见，N 一定是奇数，所以中间堆是唯一的。

请帮助贝茜确定约翰问题的答案。

输入格式：

第一行包含 N 和 K。

接下来 K 行，每行包含两个整数 A,B用来描述一个指令。

输出格式：

输出完成所有指令后，N 个干草堆的中值高度。

数据范围：

1≤N≤1e6,
1≤K≤25000，
1≤A≤B≤N，

输入样例：

7 4
5 5
2 4
4 6
3 5

输出样例：

1

错误/超时代码-------复杂度O(n*m)

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stack>
#define N 1000010
using namespace std;
int main()
{
	int n,k,j,i,a,b;
	int num[N]={0};
	cin >> n >> k;
	while (k--)
	{
		cin >> a >> b;
		for (i = a; i <= b; i++)
		{
			num[i]++;
		}
	}
	sort(num, num + n + 1);
	cout << num[n / 2 + 1];
	return 0;
}

差分做法

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N],b[N];
int n,k;
void insert(int l,int r)//建立差分数组
{
    b[l] ++;
    b[r + 1] --;
}
int main()
{
    cin >> n >> k;
    while(k --)
    {
        int l,r;
        cin >> l >> r;
        insert(l,r);
    }
    for(int i = 1; i <= n; i ++)
        a[i] = a[i - 1] + b[i];
    sort(a + 1, a + 1 + n);
    cout << a[(n + 1) / 2] << endl;
    return 0;
}