本文共 906 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：就是有一条宽为L的河，河上有n个石头，每个石头与河对岸的距离为a[i],然后青蛙过河最多跳m次，问青蛙最少需要一次跳多远才能过河。

本题就是一个二分+贪心的思想，二分L（河的距离），贪心石头之间的距离。

代码如下：

#include
   
    #include
    
     using namespace std;const int N = 500000 + 10 ;int a[N] ;int L , n , m ;int Greed(int l)//贪心{    if(m * l < L) return 0 ;    int k = 0 ;    int i = 0 , j = 1 ;    while(j <= n+1)    {        if(l < a[j] - a[i]) return 0;        while(a[j] - a[i] <= l && j <= n+1) j++;        i = j - 1 ;        k ++ ;    }    if(k > m) return 0;    return 1;}int search(int x,int y)//二分{    int mid ;    while( x <= y )    {        mid = (x + y) / 2 ;        if(Greed(mid)) y = mid - 1 ;        else x = mid + 1 ;    }    return x ;}int main(){    while(scanf("%d%d%d",&L,&n,&m)!=EOF)    {        for(int i = 1;i <= n ; i ++)        {            scanf("%d",&a[i]);        }        a[n+1] = L ; a[0] = 0 ;        sort(a+1,a+n+1);        printf("%d\n",search(0,L));    }}
    
   

转载地址：http://eusgi.baihongyu.com/