一.问题描述
一年一度“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
注:0<=M<=N<=5e4,1<=L<=1e9
二.设计思路
对于这些类似 “最短最长”、“最小最大” 等题目,我们使用二分答案来验证即可。
如果一个答案 x 可行,它要满足在跳跃的距离最短为 x 的时候,尽可能少移走石头。于是,我们统计在 x 的情况下,移走石头的数量 cnt 与题目要求的移走石头的数量 m 进行对比即可。now 代表当前所在的石头号,通过比对,如果发现间隔小于 x ,则必须进行一次移走石头,否则不能保证最短跳跃距离为 x。
下一步,我们需要对可能的答案进行二分查找即可。
三.流程图
四.伪代码
1
五.代码实现
1#include<bits/stdc++.h>
using namespace std;
int stone[50002];
int l, n, m;
bool check(int x){
int cnt = 0, now = 0;
for(int i = 1; i <= n + 1; i++){
if(stone[i] - stone[now] < x){
cnt++;
}
else{
now = i;
}
}
return cnt <= m;
}
int binary_search(int l, int r){
int ans;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)){
ans = mid;
l = mid + 1;
} else{
r = mid - 1;
}
}
return ans;
}
int main(){
cin >> l >> n >> m;
for(int i = 1; i <= n; i++){
cin >> stone[i];
}
stone[n + 1] = l;
cout << binary_search(1, l);
return 0;
}
标签:移走,int,岩石,mid,终点,打卡,每日,起点 From: https://www.cnblogs.com/leapssisbird/p/17326906.html