首页 > 代码库 > bzoj1904: Musical Water-fence
bzoj1904: Musical Water-fence
找出最高的木块,假设在这块木块上无限加水,就会形成一些水池,然后才向两侧溢出
用并查集维护当前在某个位置使水向左/右流动,水会流向哪个水池或从某一侧溢出浪费,当某个水池满时更新并查集
#include<cstdio>int n,m,mx=1,n2;double ws[1000007],hs[1000007],sum[1000007],al=0,ar=0;int f[2000007],ss[1000007],sp=0;int get(int x){ int a=x,c; while(x!=f[x])x=f[x]; while(x!=f[a])c=f[a],f[a]=x,a=c; return x;}void cal(int w){ if(w<n2)f[w]=w+n2; else f[w]=w-n2;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%lf%lf",ws+i,hs+i); if(hs[i]>hs[mx])mx=i; } ss[sp=0]=mx; for(int i=mx-1;i;--i){ while(hs[ss[sp]]<hs[i])--sp; ss[++sp]=i; } ss[++sp]=0; n2=n+2; for(int i=sp;i;--i){ for(int j=ss[i];j<ss[i-1];++j)f[j+1]=f[j+n2]=ss[i]+n2,sum[ss[i]]+=ws[j]*(hs[ss[i]]-hs[j]); } ss[sp=0]=mx; for(int i=mx+1;i<=n;++i){ while(hs[ss[sp]]<hs[i])--sp; ss[++sp]=i; } ss[++sp]=n+1; for(int i=sp;i;--i){ for(int j=ss[i];j>ss[i-1];--j)f[j-1+n2]=f[j]=ss[i],sum[ss[i]]+=ws[j]*(hs[ss[i]]-hs[j]); } for(int i=1;i<=m;++i){ int x;double s,sl,sr; scanf("%d%lf",&x,&s); sl=sr=s/2; while(sl){ int w=get(x); if(w%n2==0){ al+=sl; sl=0; }else if(w%n2==n+1){ ar+=sl; sl=0; }else if(sum[w%n2]>sl){ sum[w%n2]-=sl; sl=0; }else{ sl-=sum[w%n2]; sum[w%n2]=0; cal(w); } } while(sr){ int w=get(x+n2); if(w%n2==0){ al+=sr; sr=0; }else if(w%n2==n+1){ ar+=sr; sr=0; }else if(sum[w%n2]>sr){ sum[w%n2]-=sr; sr=0; }else{ sr-=sum[w%n2]; sum[w%n2]=0; cal(w); } } } printf("%.3f\n%.3f",al,ar); return 0;}
bzoj1904: Musical Water-fence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。