【差分】Tallest Cow（poj 3263/luogu 2879）

Tallest Cow

poj 3263

luogu 2879

题目大意：

现在有n头牛，两头牛如果要相互看到，那他们之间的牛必须比他们两低，现在给出n，最高牛的位置和高度，和m对关系，要你求每头牛最高是多少

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例：

5
4
5
3
4
4
5
5
5

解题思路：

我们可以把题目看成每一头牛被多少对牛所包围，
然后直接用最大高度减去包围此牛的牛的对数即可，
然后我们可以用差分来求出被多少对牛包围
在开头+1的地方-1，在结尾的地方+1即可

代码：

#include<cstdio>
using namespace std;
int n,p,h,m,a,b,f[10100];
bool s[10100][10100];
int main()
{
	scanf("%d %d %d %d",&n,&p,&h,&m);
	for (int i=1;i<=m;++i)
	  {
	  	scanf("%d %d",&a,&b);
	  	if (a>b) p=a,a=b,b=p;//变成a<b
	  	if (s[a][b]) continue;//计算过就不计算了
	  	f[a+1]--;//差分
	  	f[b]++;
	  	s[a][b]=1;//记录
	  }
	p=h;
	for (int i=1;i<=n;++i)
	  {
	  	p+=f[i];//计算结果
	  	printf("%d\n",p);//输出
	  }
	return 0;
}