【题解】POJ P3263 【Tallest Cow】

题面中给了M对关系,这告诉了我们牛的相对身高。我们建立一个数组C,初始为0,若一条关系A_{i}B_{i},可以相互看见(A_{i}<B{i},不满足则交换),则把C中下标为A_{i}+1B_{i}-1的数都减去1,意思是,在A_{i}B_{i}之间的牛,身高至少比他们小1。

因为第P头牛是最高的,所以最后C[P]==0,第i头牛的身高==H + C[i]

问题是怎么求,朴素求复杂度为O(NM),可以快速求:

建立一个数组D,对于每个A_{i}B_{i},令D[A_{i}+1] - 1D[b_{i}]+1。表明身高减一的影响从A_{i}+1开始,持续到B_{i}-1,在B_{i}结束。最后C就是D的前缀和。

 

对于重复关系,咱们用map解决。

#include<cstdio>
#include<map>
#include<algorithm>

namespace OI{
	using std::map;
	using std::make_pair;
	using std::pair;
	using std::swap;
}
using namespace OI;

const int MAXN = 10000 + 6;

int c[MAXN],d[MAXN];

int main(){
	int n,p,h,m;
	scanf("%d %d %d %d",&n,&p,&h,&m);
	
	map<pair<int,int>,bool> see;
	
	for(int i = 0;i < m;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		if(a > b){
			swap(a,b);
		}
		if(see[make_pair(a,b)]){
			continue;
		}
		d[a + 1]--;
		d[b]++;
		see[make_pair(a,b)] = true;
	}
	
	for(int i = 1;i <= n;i++){
		c[i] = c[i - 1] + d[i];
		printf("%d\n",h + c[i]);
	}
	printf("\n");
	
	return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注