题目链接

Garland POJ - 1759

思路

$$ 写出通项公式 H_i = 2 * H_{i - 1} - H_{i - 2} + 2 \\\\ H_1 = A , 设H_2 = X \\\\ H_i = (i - 1) * X -(i - 2) * A + (i - 1) * (i - 2) \\\\ 由此可见H_i 与 X也就是H_2成正比 \\\\ 因为H_i的图像是先减后增的，所以可以二分H_2来求解 $$

时间复杂度

$$ O(Nlog(M)) $$

代码

#include <cstdio>

using namespace std;

int n;
double a;

const double eps = 1e-8;
const int MAXN = 1e3 + 10;
double x[MAXN];
double ans;

bool check(double mid) {
    x[1] = a;
    x[2] = mid;
    for (int i = 3; i <= n; i++) {
        x[i] = x[i - 1] * 2 - x[i - 2] + 2;
        if (x[i] < 0) {
            return false;
        }
    }
    ans = x[n];
    return true;
}

int main() {

    scanf("%d%lf", &n, &a);

    double l = 0, r = a;
    for (int i = 1; i <= 100; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%.2f", ans);
    return 0;
}