Poj 1759: Garland

題目

分析

我本來想對 B 二分搜，然後反推 H2，之後計算出其它項… 我也真的這麼做了，跑去推 Hi 的通式，但發現 Hi 的通式中含有 (1 + sqrt(8)) ^ i 這種東西…這根本不能用啊

於是我們轉一下頭腦，改成對 H2 二分搜，這樣也可以推出各項

正負相關性判定

bool C(double h2) = 此時是否有任一項 < 0

C(m) 表：

0 0 0 1 1 1 1

目標是尋找第一個 1

上下界判定

解的範圍是 [0, A]，使用 (lb, ub]，所以得

double lb = -1.0;
double ub = A;

答案是 C(mid) 計算中產生的 HN，也就是 B。

判斷函式實作

題目的

Hi = (Hi-1 + Hi+1) / 2 - 1

變形為

Hi = 2 * Hi-1 - Hi-2 + 2

利用此式計算各項，看是否有任一項小於零

二分搜次數

即然是處理 double，那就用定量次數的二分搜，實測範測可知，30 次以上即可。

AC Code

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

using namespace std;

int N;
double A, B;
double H[1000+1];

bool C(double h2) {
    H[1] = A;
    H[2] = h2;
    for (int i = 3; i <= N; i++) {
        H[i] = 2.0 * H[i-1] - H[i-2] + 2.0;
        if (H[i] < 0.0)
            return false;
    }
    B = H[N];
    return true;
}

double solve() {
    // 解的範圍 = [0, A]
    // 0 0 0 1 1 1 1
    // (lb, ub]
    double lb = -1;
    double ub = A;
    for (int i = 0; i < 30; i++) {
        double mid = (lb + ub) / 2.0;
        if (C(mid)) ub = mid;
        else lb = mid;
    }

    return B;
}

int main() {
    scanf("%d %lf", &N, &A);
    printf("%.2f\n", solve());
    return 0;
}

amoshyc/poj1759.md