二分

简单题

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define maxn 50005 #define eps 10e-9 struct Cistern {
     double b, w, h, d; }cistern[maxn]; double total; int n; double v; double maxh; int dblcmp(double a, double b) {
     if (a + eps < b) return -1; if (a - eps > b) return 1; return 0; } void input() {
         total = 0;     maxh = 0;     scanf("%d", &n); for (int i = 0; i < n; i++)     {
             scanf("%lf%lf%lf%lf", &cistern[i].b, &cistern[i].h, &cistern[i].w, &cistern[i].d);         total += cistern[i].h * cistern[i].w * cistern[i].d;         maxh = max(maxh, cistern[i].h + cistern[i].b);     }     scanf("%lf", &v); } bool high(double h) {
         total = 0; for (int i = 0; i < n; i++) if (dblcmp(cistern[i].b, h) <= 0 && dblcmp(cistern[i].b + cistern[i].h, h) >= 0)             total += (h - cistern[i].b) * cistern[i].w * cistern[i].d; else if (dblcmp(cistern[i].b + cistern[i].h, h) <= 0)             total += cistern[i].h * cistern[i].w * cistern[i].d; return dblcmp(total, v) >= 0; } double binarysearch() {
     double l = 0; double r = maxh; while (dblcmp(l, r) != 0)     {
     double mid = (l + r) / 2; if (high(mid))             r = mid; else             l = mid;     } return l; } int main() {
     //freopen("t.txt", "r", stdin);     int t;     scanf("%d", &t); while  (t--)     {
             input(); if (total < v)         {
                 printf("OVERFLOW\n"); continue;         }         printf("%.2f\n", binarysearch());     } return 0; }