首页 > 代码库 > CF 371D Vessels 【并查集】

CF 371D Vessels 【并查集】

给出一个竖着的n个容器每个容器的容积,从上到下分别是1,2,3,4,,n,从某点开始浇水,保证该层满了后水能流向下一层,一层一层,直到不再溢出或者最底下都装满了留到地上去了为之。

给出n个操作/询问

在x点浇p的水

查询x点的水量

 

这题平妈想的,用并查集来做。

很容易想到暴力的方法,就是,如果是从m点开始浇水,则,我一个一个来处理m以后的点,如果这点点满了就下一个,一直到找到没满的点,慢慢地放置这些水。

这里有个很需要优化的量,我怎么快速知道从某个点开始距离它最近的有水的点位是什么(因为就算后面有的位置是满水的,如果我们走到那个位置,就会把它连成一片)。

可以用并查集实现,如果有一个位置被水填满了的话,就把它和它前一个位置连起来(如果它前一个位置是空的话)

#include <cstdio>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define in(x)   scanf("%d",&(x))
const int NN=551111;
int f[NN];
int ff[NN];
int par[NN];
void init(int n){
	for(int i=1;i<=n;i++) par[i]=i;
}
int findx(int x){
	if(par[x]==x) return x;
	else return par[x]=findx(par[x]);
}
void unite(int x,int y){
	x=findx(x);y=findx(y);
	if(x==y) return;
	int maxn=max(x,y);
	int minn=min(x,y);
	par[minn]=maxn;
}


int main(){
#ifndef ONLINE_JUDGE
	freopen("G:/in.txt","r",stdin);
#endif
	int n;
	//cin>>n;
	in(n);
	init(n);
	for(int i=1;i<=n;i++) cin>>f[i];
	for(int i=1;i<=n;i++) ff[i]=f[i];
	int m;
	//cin>>m;
	in(m);
	for(int i=1;i<=m;i++){
		int kind;cin>>kind;
		if(kind==1){
			int p,x;
			//cin>>p>>x;
			in(p);in(x);
			if(x>f[p]){
				x-=f[p];
				f[p]=0;
				if(p>=2 && p<=n && f[p-1]==0){
                    unite(p,p-1);
                }
				int st=findx(p)+1;
				//unite(st,st-1);
				while(x>=f[st] && st<=n){
					unite(st,st-1);
					x-=f[st];
					f[st]=0;
					st++;
				}
				if(x && st<=n)
					f[st]-=x;
			}else if(x<f[p]){
				f[p]-=x;
			}else{
                x=0;
                f[p]=0;
                if(p>=2 && p<=n && f[p-1]==0){
                    unite(p,p-1);
                }
            }
		}else{
			int p;in(p);
			//cout<<ff[p]-f[p]<<endl;
			printf("%d\n",ff[p]-f[p]);
		}
	}
	return 0;
}


 

CF 371D Vessels 【并查集】