Home POJ - 3263 差分 + 前缀和
Post
Cancel

POJ - 3263 差分 + 前缀和

给出 n 头牛的身高,和 m 对关系(a[i] 与 b[i] 可以相互看见。即他们中间的牛都比他们矮)。已知最高的牛为第 p 头,身高为 h,求每头牛的身高最大可能是多少。

只需不断维护相对值的前缀就能得到解

这种思想第一次是在树状数组区间更新那里看到的,由于题目要求是 1~n 所以直接可以用前缀和维护

注意不能直接 -1 +1

/*H E A D*/
int delta[maxn];
map<P,int> vis;
int main(){
	int n,I,h,r,a,b;
	while(~iin(n)){
	    I=read();h=read();r=read();
		memset(delta,0,sizeof delta);
		vis.clear();
		rep(i,1,r){
			a=read();b=read();
			if(a>b) swap(a,b);//strict prefix
			if(vis[P(a,b)]) continue;
			vis[P(a,b)]=1;
			delta[a+1]--;delta[b]++;//-1 +1
		}
		rep(i,1,n){
			delta[i]+=delta[i-1];
		}
		rep(i,1,n){
			println(delta[i]+h);
		}
	}
	return 0;
}
This post is licensed under CC BY 4.0 by the author.