【gzoj1564】水塔水位【离散化】

本文主要是介绍【gzoj1564】水塔水位【离散化】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个物理上的连通器（如图），问加入一些水之后，水位的高度是多少（地面高度为0）。
在这里插入图片描述

分析

一开始的做法是n方的暴力，也就是暴力判断有没有高度区间涵盖。然后T掉一个点，疯狂卡常卡时间，结果感觉超时挺多的。
code：

for(register int i=1;i<=2*n-1;i++)
{int s=0,v=0;for(register int j=1;j<=n;j++){if(b[j]<=a[i]&&b[j]+h[j]>=a[i+1]){s+=w[j]*d[j];v+=w[j]*d[j]*(a[i+1]-a[i]);}}if(v<tot) tot-=v,ans=a[i+1];else if(v>tot){double t1=tot,t2=s;ans+=t1/t2;break;}else if(v==tot){ans=a[i+1];break;} 
}

然后老师走过来一脸鄙视：你这个怎么写的这么啰嗦，直接扫描线一样扫过去就行啦，你判断一下这个是上底还是下底再对面积做处理啊。

就有了现在的做法，记录上底面还是下底面，实时计算面积然后乘上当前枚举区间的高度，判断是否装满就行，复杂度 $O (n)$ 。

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct node
{int s,ty,w,d;
}a[100010];int n,tot,b[50010],h[50010],w[50010],d[50010];
long long amount;
double ans;int cmp(node l,node r)
{return l.s<r.s;
}int main()
{scanf("%d",&n);for(register int i=1;i<=n;i++){scanf("%d%d%d%d",&b[i],&h[i],&a[i].w,&a[i].d);amount+=h[i]*a[i].w*a[i].d;a[i].s=b[i];a[i].ty=0;a[i+n].s=b[i]+h[i];a[i+n].ty=1;a[i+n].w=a[i].w;a[i+n].d=a[i].d;}scanf("%d",&tot);if(amount<tot){printf("OVERFLOW");return 0;}sort(a+1,a+2*n+1,cmp);int s=0,v=0;for(int i=1;i<=2*n-1;i++){if(a[i].ty==0) s+=a[i].w*a[i].d;else s-=a[i].w*a[i].d;v=s*(a[i+1].s-a[i].s);if(v<tot) tot-=v,ans=a[i+1].s;else if(v>tot){double t1=tot,t2=s;ans+=t1/t2;break;}else if(v==tot){ans=a[i+1].s;break;} }printf("%.2lf",ans);return 0;
}