本文主要是介绍hdu 4004题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-hdu- 4004
题目大意：在宽度为L的河上给定n个落脚点，位置分别给出，通过最多m次跳跃来过河，问我们其中跳跃距离最远的那个值是多少。
题目解析：设ans是相邻落脚点之间的最大距离，所以结果值的范围是【ans, L】。利用二分法缩小这个范围。mid = (left+right)/2;跳跃能力是mid值，如果跳跃次数solve（mid）<=m，则right = mid；mid = (left+right)/2;缩小跳跃距离，如果跳跃次数超过m值就left = mid+1; mid = (left+right)/2;来扩大跳跃距离。
代码如下：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int a[500005];
const int INF = 2000000000;
int L, n, m;
int solve(int len){ //根据len长度的跳跃能力，返回需要跳跃的次数
intcount = 0, i = 0, tlen = 0;
while(tlen < L ){
tlen+= len;
while(a[i] <= tlen ){
i++;
}
tlen= a[i-1];
count++;
}
returncount;
}
int binary_search(int l, int r){ //利用二分查找将跳跃距离缩小范围
intright = r, left = l, mid;
while(left < right ){
mid= (right + left)/2;
if(solve(mid) <= m ){ //如果次数满足要求值，则缩小范围
right= mid;
}else{ //否则扩大范围
left= mid+1;
}
}
returnleft;
}
int main()
{
inti, j;
while(scanf("%d%d%d", &L, &n, &m) != EOF ){
for(i = 0; i < n; i ++ ) scanf("%d",&a[i]);
a[n]= L; //第n+1个点的位置默认为 L 值
a[n+1]= INF;
sort(a,a+n);
intans = a[0];
for(i = 1; i <= n; i ++ ){ //ans 为相邻两站之间的最大间距
if(a[i]- a[i-1] > ans ) ans = a[i] - a[i-1];
}
ans= binary_search(ans, L);
printf("%d\n",ans);
}
return0;
}
这篇关于hdu 4004题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
