洛谷P10909题（2024年蓝桥杯国B）：用二分查找+动态规划解决立定跳远问题

一、题目解读

洛谷P10909题是一个关于跳跃游戏的算法问题，要求玩家在给定限制条件下找到最小的跳跃能力值L。题目核心在于如何高效判断某个L值是否满足要求，并利用二分查找优化搜索过程。难点在于处理"爆发技能"这一特殊机制，该技能允许玩家在特定情况下将跳跃距离临时翻倍。

二、解题思路

1. 二分查找框架：通过二分法在可能的最小和最大L值之间搜索最优解

2. 验证函数check()：核心验证逻辑分为两种情况：

• 不使用爆发技能时的常规跳跃判断

• 使用爆发技能时的特殊处理（可跳过2L距离）

3. 边界处理：特别处理n=1的特殊情况，以及爆发技能在序列末尾的使用机会

三、解题步骤

1. 读取输入数据并处理n=1的特殊情况

2. 初始化二分查找的左右边界（left=1, right=最大距离）

3. 在每次二分迭代中：

• 计算中间值mid

• 分别验证使用/不使用爆发技能的情况

• 根据验证结果调整搜索边界

4. 输出最终找到的最小L值

四、完整代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool check(long long L, const vector<int>& a, int m, bool use_boost) {
    int cnt = 0;
    long long prev = 0;
    bool boost_used = false;
    
    for (int i = 0; i < a.size(); ++i) {
        long long dist = a[i] - prev;
        if (use_boost && !boost_used && dist > L) {
            // 尝试在此处使用爆发技能
            if (dist <= 2 * L) {
                boost_used = true;
                prev = a[i];
                continue;
            }
        }
        
        if (dist > L) {
            cnt += (dist - 1) / L;
            if (cnt > m) return false;
        }
        prev = a[i];
    }
    
    // 如果使用爆发技能但没用上，尝试在最后使用
    if (use_boost && !boost_used) {
        long long last_dist = a.back() - (a.size() > 1 ? a[a.size()-2] : 0);
        if (last_dist > L && last_dist <= 2 * L) {
            boost_used = true;
        }
    }
    
    return cnt <= m && (!use_boost || boost_used);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 处理特殊情况：n=1时只需要跳一次
    if (n == 1) {
        cout << (a[0] + 1) / 2 << endl;
        return 0;
    }
    
    long long left = 1, right = a.back(), ans = a.back();
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (check(mid, a, m, false) || check(mid, a, m, true)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

五、总结

本解法通过二分查找将时间复杂度优化至O(n log D)，其中D是最大距离。爆发技能的智能使用策略是本算法的亮点，通过在check函数中动态判断最佳使用时机，既保证了正确性又提高了效率。这种思路可以推广到其他带有特殊技能机制的算法问题中。