HDU4004

题目大意，有一条长度为L和河流，中间穿插n个石凳，青蛙跳m次经过石凳后到达对岸，求青蛙每次跳跃的最大距离的最小值

本题数据量大n<500000,显然简单的o(n*n)算法是通过不了的，在输入大量的数据使用scanf比使用cin快很多，而且cin会超时，scanf可以AC，大致思路是：青蛙跳跃能力的范围·在两个石凳间最大差值L0与两岸距离L之间，算法步骤如下：

1.求出两岸最大距离L0，二分左边界left=L0,右边界right=L

2判断mid=（left+right）>>1是否可以在跳跃m次以内（包括m）到达对岸，具体做法通过贪心来完成，尽量每一次跳跃跨过的石凳最远，这样可以使跳跃的总次数最小

3不断将区间二分，最终left==right时，left就是要求的值

#include<iostream>
#include<algorithm>
using namespace std;
bool Check(int a[], int n, int m, int x);
int a[500002];
int main(){
a[0] = 0; //初始位置
int l, n, m, left, right, i, mid;
while (cin >> l >> n >> m){
for (i = 1; i < n + 1; i++)
scanf("%d",&a[i]);
sort(a, a + n+1); //输入的距离排序
a[n+1] = l, //末位置
left = a[1]; //将left可以随便设置一个初始值
right = l; //右边界
n = n + 2; //加上初始位置和末位置，a中一共有n+2个位置
while (left <right){
mid = (left + right)/2;
if (!Check(a, n, m, mid)) //如果跳跃m次不能通过
left = mid + 1;
else
right = mid; //若果mid通过，那么mid-1不确定是否通过
}/*左右边界相等时跳出循环*/
cout << left << endl;
}
return 0;
}
bool Check(int a[], int n, int m, int x){
int i = 0, step = 0, j = 1;
bool flag;
while (j<n){
flag = 1;
while (j< n&&a[j] - a[i] <= x){
j++; //贪心，尽可能多的通过石凳
flag = 0;
}
i = j - 1;
if (flag) //说明x比某两个石凳间距离还要小
return 0;
step++;
if (step>m) //跳跃·的次数大于m还未到达对岸
return 0;
}
return 1;
}

巴特西

HDU4004

最新文章

热门文章