[数据结构与算法]牛客 Tallest Cow 题解 （差分）

原题链接：https://ac.nowcoder.com/acm/contest/999/C
解题思路：利用差分数组， 如果A牛和B牛可以互相看见，那么[A, B]之间所有牛的身高应该减一， 这时候用差分数组记录，当所有关系都记录之后，从第一头牛开始，挨个遍历每头牛的身高和最高的牛的差距，最后输出
注意：用map检验这个关系是否出现过

make_pair就是将（a, b）结合成一个数据，相当于建立一个新的结构体，里面有a, b

#include<iostream>
#include<map>
#include<utility>

using namespace std;

const int N = 1e4 + 10;

map<pair<int, int>, bool>ex;

int d[N], c[N];
int n, m, h, p;

int main()
{
	cin>>n>>p>>h>>m;
	for(int i = 1; i <= m; i ++ ){
		int a, b;
		cin>>a>>b;
		if(a > b) swap(a, b);
		if(ex[make_pair(a, b)]) continue;//如果这组数据出现过，直接进入下一次循环 
		//d[]相当于c的差分数组，记录从a+1到b都-1 
		d[a + 1] -- ;
		d[b] ++ ;
		ex[make_pair(a, b)] = true;
	}
	for(int i= 1; i <= n; i ++ ){
		c[i] = c[i -1] + d[i];//计算c[]数组，即每头牛和最高的牛的最小差距 
		cout<<c[i] + h<<endl;//最小差距加上最高牛的高度，就是每头牛的高度 
	}
	return 0;
}