题目链接：uva 1356 - Bridge

题目大意：在一座长度为B的桥上建若干个塔，塔的间距不能超过D，塔的高度为H，塔之间的绳索形成全等的抛物线。绳索的总长度为L。问在建最少塔的情况下，绳索的最下段离地面的高度。

解题思路：贪心的思想求出最少情况下建立的塔数。
二分高度，然后用积分求出两塔之间绳索的长度。

C++ 积分#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; double f (double a, double x) { double aa = a * a, xx = x * x;; return (x * sqrt(aa + xx) + aa * log(fabs(x + sqrt(aa + xx)))) / 2; } double parabola_length (double w, double h) { double a = 4 * h / (w * w); double b = 1.0 / (2 * a); return (f(b, w/2) - f(b, 0)) * 4 * a; } double bsearch (double l, double r, double d, double v) { while (r - l > 1e-5) { double mid = (r + l) / 2; if (parabola_length(d, mid) < v) l = mid; else r = mid; } return l; } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { int D, H, B, L; scanf("%d%d%d%d", &D, &H, &B, &L); int n = (B + D - 1) / D; double d = B * 1.0 / n; double l = L * 1.0 / n; if (kcas > 1) printf("\n"); printf("Case %d:\n%.2lf\n", kcas, (double)H - bsearch(0, H, d, l)); } return 0; } 
      
     
    
   

C++ 辛普森#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; double A; double f (double x) { return sqrt (1 + 4 * A * A * x * x); } double simpson (double a, double b) { double c = (a + b) / 2; return (f(a) + 4*f(c) + f(b)) * (b-a) / 6; } double asr (double a, double b, double eps, double S) { double c = (a + b) / 2; double L = simpson(a, c), R = simpson(c, b); if (fabs(L+R-S) <= eps * 15) return L + R + (L + R - S) / 15; return asr(a, c, eps/2, L) + asr(c, b, eps/2, R); } double asr (double a, double b, double eps) { return asr(a, b, eps, simpson(a, b)); } double parabola_length (double w, double h) { A = 4 * h / (w * w); return asr(0, w / 2, 1e-5) * 2; } double bsearch (double l, double r, double d, double v) { while (r - l > 1e-5) { double mid = (r + l) / 2; if (parabola_length(d, mid) < v) l = mid; else r = mid; } return l; } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { int D, H, B, L; scanf("%d%d%d%d", &D, &H, &B, &L); int n = (B + D - 1) / D; double d = B * 1.0 / n; double l = L * 1.0 / n; if (kcas > 1) printf("\n"); printf("Case %d:\n%.2lf\n", kcas, (double)H - bsearch(0, H, d, l)); } return 0; }