蓝桥杯第十五届决赛真题-立定跳远 二分答案

解题思路: 从题目我们了解到，可以有一次机会跳2L远，所以我们就当作多一个跳跃点即可，换句话说，我们初始的可设置的跳跃点有m+1个。这样问题就变得简单了，我们发现问题具有二段性，即大于最小L的都可以完成这个项目，小于最小L的都不能完成项目，所以考虑二分答案。


参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N];

int n, m;

bool check(int mid)

{

    int cnt = m;

    for (int i = 1; i < n; i++)

    {

        int t = a[i] - a[i - 1];

        if (mid < t)

        {

            if (t % mid == 0)

            {

                cnt -= (t / mid - 1);

                if (cnt < 0) return false;

            }

            else

            {

                cnt -= (t / mid);

                if (cnt < 0) return false;

            }

        }

    }

    return true;

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    m++;

    int l = 1, r = 1e8 + 1;

    while (l < r)

    {

        int mid = (l + r) >> 1;

        if (check(mid)) r = mid;

        else l = mid + 1;

    }

    cout << r;

    return 0;

}