HDU4004 二分+贪心

题目链接

题意：青蛙通过河中央的 n 块石头过河， 所有石头均在与河岸垂直的一条线上，给定每块石头到河岸的距离，河宽 L，青蛙跳的次数最大值 m，求出青蛙能够过河的最小步长。

当步长为河宽时，青蛙必能跳过，二分步长，求最小步长。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int l, n, m;
int len[500005];

bool judge(int x){
    if(x*m < l) return 0;
    int sum = 0;
    int y = x;
    int k = 0;
    int flag = 1;
    for(int i = 0; i <= n; i++){
        int cha = len[i+1]-len[i];
        if(x >= cha){
            x -= cha;
            if(i==n) k++;
            flag = 0;
        }else{
            if(flag) return 0;
            k++;
            x = y;
            i--;
            flag = 1;
        }
    }
    if(k > m) return 0;
    return 1;
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d%d%d", &l, &n, &m) != EOF){
        len[0] = 0;
        for(int i = 1; i <= n; i++)
            scanf("%d", &len[i]);
        len[n+1] = l;
        sort(len+1, len+1+n);
        int L = 0, R = l;

        while(L <= R){
            int mid = L+(R-L)/2;
            if(judge(mid))
                R = mid-1;
            else L = mid+1;
        }
        cout << L << endl;
    }
    return 0;
}