题意分析

题目描述：
有一排灯，每个灯的高度必须满足以下条件：

1. 第一个灯的高度为给定值 A。
2. 从第三个灯开始，每个灯的高度必须满足公式：h[i] = -h[i-2] + 2*h[i-1] + 2。
3. 所有灯的高度必须严格大于0。

你的任务是找到一个最小的初始值 h[2]，使得所有后续灯的高度都满足条件，并输出最后一个灯 h[n] 的高度。

关键问题转化

1. 递推关系：
   每个灯的高度由前两个灯的高度决定，形成一个递推序列： [ h[i] = -h[i-2] + 2h[i-1] + 2 \quad (i \geq 3) ]

2. 约束条件：
   所有灯的高度必须严格大于0，即： [ h[i] > 0 \quad \forall i \in [1, n] ]

3. 目标：
   找到最小的 h[2]，使得整个序列满足条件，并计算最终的 h[n]。

解题思路

核心观察

• 单调性：h[2] 越大，后续的 h[i] 也越大。因此，可以使用二分查找来找到最小的合法 h[2]。
• 可行性检查：对于给定的 h[2]，通过递推公式计算所有 h[i]，检查是否所有高度都大于0。

算法步骤

1. 二分查找范围：
   设置初始范围 [L, R]，其中 L = 0（理论下界），R 设置为一个足够大的值（如 1e10）。

2. 二分查找过程：

   • 取中间值 mid，检查以 h[2] = mid 为初始值生成的序列是否合法。
   • 如果合法，说明可能存在更小的 h[2]，缩小右边界 R = mid。
   • 如果不合法，说明 h[2] 太小，增大左边界 L = mid。

3. 可行性检查：
   从 h[1] = A 和 h[2] = mid 开始，递推计算每个 h[i]，一旦发现某个 h[i] ≤ 0，立即返回 false。

代码实现与解析

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <limits.h>
#include <math.h>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
double res;
int n;
double A;
double *arr;

// 检查 h[2] = mid 时是否所有 h[i] > 0
bool Ok(double mid) {
    arr[2] = mid;
    for (int i = 3; i <= n; i++) {
        double temp = -arr[i-2] + 2*arr[i-1] + 2;
        if (temp <= 0) {
            return false;
        }
        arr[i] = temp;
    }
    return true;
}

int main() {
    while (scanf("%d%lf", &n, &A) != EOF) {
        double L = 0.0;
        double R = 1e10;
        arr = new double[n+1];
        arr[1] = A;
        
        // 二分查找最小的合法 h[2]
        for (int i = 0; i < 100; i++) {
            double mid = L + (R - L) / 2;
            if (Ok(mid)) {
                R = mid;  // 存在更小的可能
            } else {
                L = mid;  // 需要更大的值
            }
        }
        
        // 输出最终结果（保留两位小数）
        printf("%.2f\n", arr[n]);
        delete[] arr;  // 释放内存
    }
    return 0;
}

算法关键点解析

1. 二分查找的精度控制：
   通过固定迭代次数（100次）确保精度足够高，每次迭代将搜索范围缩小一半，最终误差约为 1e-30，远小于题目要求的精度。

2. 可行性检查函数 Ok：

   • 从 h[2] = mid 开始，递推计算每个 h[i]。
   • 一旦发现某个 h[i] ≤ 0，立即返回 false，终止计算。

3. 内存管理：
   使用动态数组 arr 存储灯的高度，确保处理大 n 时不会栈溢出，并在使用后释放内存。

复杂度分析

• 时间复杂度：(O(n \log M))，其中 (n) 是灯的数量，(M) 是二分查找的范围。由于迭代次数固定为100次，实际复杂度为 (O(100n) = O(n))。
• 空间复杂度：(O(n))，用于存储每个灯的高度。

测试用例分析

输入示例：

3 10.0

输出示例：

24.00

解释：

• 当 n = 3，A = 10.0 时，最小的 h[2] 使得所有灯高度为正的解为 h[2] = 4.0。
• 计算得到 h[3] = -h[1] + 2h[2] + 2 = -10 + 8 + 2 = 0，刚好满足条件。
• 最终输出 h[3] = 24.00（四舍五入保留两位小数）。