首页 > 代码库 > poj1434Fill the Cisterns!（二分）

poj1434Fill the Cisterns!（二分）

2024-07-15 15:14:54   222人阅读

链接

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

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

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 5000512 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 struct node18 {19     int b,h,w,d;20 }p[N];21 int dcmp(double x)22 {23     if(fabs(x)<eps) return 0;24     return x<0?-1:1;25 }26 double cal(double mid,int n)27 {28     int i;29     double s = 0;30     for(i = 1; i <=n;i++)31     {32         if(p[i].b>mid) continue;33         s+=min(mid-p[i].b,p[i].h*1.0)*p[i].w*p[i].d;34     }35     return s;36 }37 int main()38 {39     int v,n,i,t;40     cin>>t;41     while(t--)42     {43         scanf("%d",&n);44         double s = 0;45         for(i =1 ; i <=n; i++)46         {47             scanf("%d%d%d%d",&p[i].b,&p[i].h,&p[i].w,&p[i].d);48             s+=p[i].h*p[i].w*p[i].d;49         }50         scanf("%d",&v);51         if(dcmp(v-s)>0)52         {53             puts("OVERFLOW");54             continue;55         }56         double rig = 2000000.0,lef = 0,mid;57         while(rig-lef>eps)58         {59             mid = (rig+lef)/2.0;60             if(dcmp(cal(mid,n)-v)>=0)61             rig = mid;62             else lef = mid;63         }64         printf("%.2f\n",rig);65     }66     return 0;67 }
View Code

 


联系
我们