uva 1356 - Bridge(积分+二分)

本文主要是介绍uva 1356 - Bridge(积分+二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 1356 - Bridge

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

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

 C++ 积分
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>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;elser = 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 <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>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;elser = 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;
}