当前位置：首页 > 蓝桥杯 > 洛谷P10909题（2024蓝桥杯国B）：二分查找+贪心算法解决立定跳远

洛谷P10909题（2024蓝桥杯国B）：二分查找+贪心算法解决立定跳远

2天前

一、题目解读

洛谷P10909是一道典型的贪心策略问题，要求在一个递增数列中，通过跳跃到达终点，并允许使用一次“爆发技能”以扩大单次跳跃距离。题目核心在于如何在限定跳跃次数内，合理分配普通跳跃与技能使用，找到最优的最大跳跃距离。

二、解题思路

1. 核心思想：采用二分查找确定最大可行跳跃距离。由于跳跃次数与距离呈反比关系，可通过二分法缩小解的范围。

2. 贪心优化：引入“爆发技能”的两种使用场景——中途遇长距离时使用，或末尾补用（若未使用过）。通过检查函数判断当前距离是否满足条件，并优先利用技能减少总次数。

三、解题步骤

1. 输入处理：读取n（元素数量）、m（最大跳跃次数）及数列a。

2. 特殊情况：n=1时直接输出(a[0]+1)/2，避免二分退化。

3. 二分查找区间：left=1，right=末尾元素值，通过mid=(left+right)/2迭代。

4. 检查函数逻辑：

○ 遍历数列，计算相邻距离dist。

○ 若use_boost且未使用技能，且dist>mid但≤2*mid，则触发技能并更新位置。

○ 若dist>mid，按普通规则累加跳跃次数（cnt）。

○ 末尾检查：若技能未用且末尾距离符合条件，补用技能。

5. 二分终止条件：找到满足check(mid, m, false)或check(mid, m, true)的最大mid值。

四、代码与注释

#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;
}