花环灯问题

一 问题描述

新年花环由 N 个灯组成，这些灯连接到公共电线上，该电线垂直固定在最外面灯上，电线以特定方式在灯的重量下下垂：每个灯悬挂在两个相邻灯的平均高度低1毫米的高度处。最左边的灯挂在地面以上 A 毫米的高度。您必须确定最右侧灯泡的最低高度 B，以便花环中的灯泡不会落在地面商，尽管一些灯泡可能会接触到地面。这个问题会忽略灯的大小。通过用 1 到 N 的整数对灯进行编号，并以毫米为单位表示第 i 个灯的高度 Hi，我们推导出以下等式。

H1 = A

Hi = (Hi-1 + Hi+1)/2 - 1, 对于所有 1 < i < N

HN = B

Hi >= 0, 对于所有 1 <= i <= N

下图所示具有 8 个灯的样品花环具有 A = 15 和 B = 9.75。

二 算法说明

根据高度 Hi = (Hi-1 + Hi+1)/2 - 1，整理该公式得到 Hi+1)=2*Hi-Hi-1 + 2.

1 二分搜索。初始时，num[1]=A，l=0.0，r = inf（无穷大，通常0x3f3f3f），mid=(r+l)/2。判断第2个灯的高度为 mid 是否可行，如果可行，则让 r = mid，缩小高度搜索，否则 l=mid，增加高度搜索。

2 判断 mid 是否可行。让 num[2] = mid，根据公式从左向右推导，num[i]=2*num[i-1]-num[i-2]+2,如果在推导过程中 num[i]<eps,则说明不可行，返回 false。注意不要写小于0，否则由于精度问题会出错。eps 是一个较小的数，例如 le-7。

3 可以用 r-l>eps 判断循环条件，也可以搜索到较大次数时停止，例如 100 次，运行 100 次二分搜索可以达到 10 的 -30 的精度范围。实际对于输入样例，运行 43 次已经找到答案，为了保险起见，尽量执行较大的次数，时间相差不大。

三 代码

package com.platform.modules.alg.alglib.poj1579;

public class Poj1759 {
    public String output = "";

    private static int inf = 0x3f3f3f3f;
    private static int maxn = 1006;
    private static double eps = 1e-7;

    private int n;
    double A;
    double num[] = new double[maxn];
    Double ans;

    // 判断第二个灯的高度为 mid 是否可行
    boolean check(double mid) {
        num[2] = mid;
        for (int i = 3; i <= n; i++) {
            num[i] = 2 * num[i - 1] - num[i - 2] + 2;
            if (num[i] < eps) return false; // 写小于 0 由于精度问题会出现问题
        }
        ans = num[n];
        return true;
    }

    void solve() {
        num[1] = A;
        double l = 0.0;
        double r = A;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (check(mid))
                r = mid;
            else
                l = mid;
        }
    }

    public String cal(String input) {
        String[] words = input.split(" ");
        n = Integer.parseInt(words[0]);
        A = Double.parseDouble(words[1]);
        solve();
        output = String.format("%.2f", ans);
        return output;
    }
}

四 测试