POJ - 3263 Tallest Cow(简单差分)

题目链接：点击查看

题目大意：给定一排n只奶牛，和最高的奶牛，再给出m个条件，a b表示a能看到b，问满足条件后每只奶牛的最大高度

题目分析：a能看到b，就表示a的高度大于等于b，再加上a和b之间的高度必须小于b，所以每次操作可以让闭区间[a+1,b-1]内的奶牛高度都减一即可简单差分，注意记得判重

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<sstream>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=1e4+100;

int a[N];

set<pair<int,int> >s;

int main()
{
//	freopen("input.txt","r",stdin);
	int n,I,H,R;
	while(scanf("%d%d%d%d",&n,&I,&H,&R)!=EOF)
	{
		memset(a,0,sizeof(a));
		s.clear();
		while(R--)
		{
			int x,y;
			scanf("%d%d",&x,&y);//x和y大小不定
			int mmax=max(x,y);
			int mmin=min(x,y);
			if(s.insert(make_pair(mmin,mmax)).second)//用set判重
			{
				a[mmin+1]--;
				a[mmax]++;
			}
		}
		int b=H;
		for(int i=1;i<=n;i++)
		{
			b+=a[i];
			printf("%d\n",b);
		}
	}
	
	
	
	
	 
	 
	
	
	
	
	return 0;
}