poj1434Fill the Cisterns!(二分)

时间:2023-12-16 08:24:32

链接

题目说给你n个水箱,初始是没有水的,每个的高低位置可能不同,给了你初始的水箱底部所处的水平线位置,问给你V体积水时,水的水平线位置。

直接二分位置p,对于每一个底部低于水平线位置的水箱,里面的水的体积 = min(h,p-b)*w*d;

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 50005
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct node
{
int b,h,w,d;
}p[N];
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double cal(double mid,int n)
{
int i;
double s = ;
for(i = ; i <=n;i++)
{
if(p[i].b>mid) continue;
s+=min(mid-p[i].b,p[i].h*1.0)*p[i].w*p[i].d;
}
return s;
}
int main()
{
int v,n,i,t;
cin>>t;
while(t--)
{
scanf("%d",&n);
double s = ;
for(i = ; i <=n; i++)
{
scanf("%d%d%d%d",&p[i].b,&p[i].h,&p[i].w,&p[i].d);
s+=p[i].h*p[i].w*p[i].d;
}
scanf("%d",&v);
if(dcmp(v-s)>)
{
puts("OVERFLOW");
continue;
}
double rig = 2000000.0,lef = ,mid;
while(rig-lef>eps)
{
mid = (rig+lef)/2.0;
if(dcmp(cal(mid,n)-v)>=)
rig = mid;
else lef = mid;
}
printf("%.2f\n",rig);
}
return ;
}