题解 | #跳石头#

解析

按照答案二分

跳跃距离为0~L

二分判断条件是所有小于跳跃距离的的数量

细节：

• 右边界找到的结果是大于待查找结果的第一个元素，在这个题目中，就相应地转化为小于目标元素的第一个值，答案为l+1或r+1
• 若想答案为l或r，check函数改成

bool check(int k){
    int ans = 0;
    for(int i = 1,j = 0;i <= n;i ++){
        if(s[i] - s[j] < k)ans++;
        else j=i;
    }
    return ans <= m;
}

代码

using namespace std;

const int N = 1e5+10;
int s[N];
int L,n,m;

bool check(int k){
    int ans = 0;
    for(int i = 1,j = 0;i <= n+1;i ++){	//模拟从上一个跳跃过来，得到跳跃距离
        if(s[i] - s[j] <= k)ans++;
        else j=i;
    }
    return ans <= m;
}

int main(){
    cin >> L >> n >> m;
    for(int i = 1;i <= n;i ++)cin >> s[i];
    s[n+1] = L;
    
    int l = 0,r = L;
    while(l < r){						//右边界二分
        int mid = (l+r+1)/2;
        if(check(mid))l = mid;
        else r = mid-1;
    }
    cout << l+1 << endl;
}