首页 > 代码库 > UVA1555-- Garland(推导+二分)

UVA1555-- Garland(推导+二分)

题目链接

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

路:Hi=(Hj+1+Hj?1)/2?1,Hi+1=2?Hi?Hi?1+2
当我们已知H1时,我们就可以二分枚举H2,求出符合题意的最小的B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const double MAXN = 2000; 
const int N = 1000; 

int n;
double A, B, H[N];

int judge(double mid) {
    H[2] = mid;
    for (int i = 3; i <= n; i++) {
        H[i] = 2 * H[i - 1] - H[i - 2] + 2;
        if (H[i] < 0) 
            return false; 
    }
    B = H[n];
    return true;
}

int main() {
    while (scanf("%d %lf", &n, &A) != EOF) {
        memset(H, 0, sizeof(H));
        double L = 0, R = MAXN, mid;
        H[1] = A;
        while (R - L > 1e-8) {
            mid = (L + R) / 2;
            if (judge(mid)) 
                R = mid;
            else
                L = mid;
        }
        printf("%.2lf\n", B);
    }
    return 0;
}