hdoj 4004 The Frog's Games 【二分要细心】【好题】

The Frog's Games

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 4767 Accepted Submission(s): 2306

Problem Description

The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they
are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).

Input

The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.

Output

For each case, output a integer standing for the frog's ability at least they should have.

Sample Input

Sample Output

4
11

题意：有一条长为len的河，河上有N个落脚点（石头），已经给出每个落脚石到青蛙起点（河的一边）的距离。要求青蛙最多用M次跳跃从起点到达对岸，问你青蛙跳跃的最小距离。

思路：二分查找，用数组存储每个落脚石到起点的距离，把对岸当做一个落脚石且它到起点距离为len。升序排列后，就是二分枚举跳跃长度mid + 判断当前值mid是否可行。

还以为会WA，没想到1A了。O(∩_∩)O~~

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 500000+1
using namespace std;
int len, N, M;
int d[MAXN];
bool judge(int D)
{
    int sum = 0, s = 0;//sum表示跳跃次数 s表示当前起点
    if(D < d[0]) return false;
    for(int i = 0; i <= N;)
    {
        if(d[i] - s <= D)
        {
            if(d[i] - s == D || i == N)//最后一个石头的判定不能少
            {
                sum++;
                s = d[i];//更替起点
            }
            i++;
        }
        else
        {
            sum++;
            s = d[i-1];//更替起点
            //若石头i 和 石头i-1距离 大于D
            if(d[i] - s > D)//不能少 要不会死循环 
                return false;
        }
    }
    return sum <= M;
}
int main()
{
    while(scanf("%d%d%d", &len, &N, &M) != EOF)
    {
        for(int i = 0; i < N; i++)
            scanf("%d", &d[i]);
        d[N] = len;//把终点看做一个石头
        sort(d, d+N+1);//升序排列
        int left = 0, right = len;
        int mid, ans;
        while(right >= left)
        {
            int mid = (left + right) >> 1;
            if(judge(mid))
            {
                ans = mid;
                right = mid - 1;
            }
            else
                left = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

hdoj 4004 The Frog's Games 【2分要细心】 【好题】

The Frog's Games

相关推荐

hdoj 4004 The Frog's Games 【2分要细心】【好题】