UVA1555-- Garland(推导+二分)

题意：有n个灯，给定第一盏灯A的高度，接下去每盏灯的高度按照公式计算，求使所有灯都不会落在地上（允许碰触）的B的最低高度。

uva 输出 double 用 %f，这一波坑的！

 1 #include <cstdio>
 2 int n;
 3 double A, B, a[1005];
 4 //h2的值
 5 bool check(double x) {
 6     a[2] = x;
 7     for(int i = 3; i <= n; ++i) {
 8         a[i] = 2 * a[i - 1] + 2 - a[i - 2];
 9         if(a[i] < 0) return false;
10     }
11     B = a[n];
12     return true;
13 }
14
15 int main() {
16     scanf("%d%lf", &n, &A);
17     a[1] = A;
18     double l = -1, r = 1e3 + 1;
19     for(int i = 0; i < 100; ++i) {
20         double mid = (l + r) / 2;
21         if(check(mid)) r = mid;
22         else l = mid;
23     }
24     printf("%.2f\n", B);
25     return 0;
26 }

View Code