The Frog‘s Games

6 1 2
2
25 3 3
11 
2
18

4
11

题目大意：l表示河的宽度，n表示河中能站石头的个数，m表示青蛙能跳的最多次数，下面跟n组数据，分别表示石头距离开始的位置，求青蛙至少一次跳多远，才能在m次及以内到对岸！

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[500005];
int main()
{
    int l,ll,n,m,max,sum;
    int i,j,cont,t;
    while(~scanf("%d%d%d",&l,&n,&m))
    {
        max=0;sum=0;
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n+1);//对石头从近到远排序
            for(i=1;i<=n;i++)
        {
            if(a[i]-a[i-1]>max)
                max=a[i]-a[i-1];//找出石头间的最大间距
        }
        if(l-a[n]>max)
            max=l-a[n];//对岸和最后一个石头也要算

        for(j=max;j<=l;j++)//枚举青蛙能跳的距离，进行验证
        {

            i=1;cont=1;t=0;ll=l;
            while(l>0&&i<=n)
            {
                ll-=a[i]-a[i-1];
                if(a[i]-t>j)
                {cont++;t=a[i-1];}
                if(i==n)
                {
                    if(l-t>j)
                        {cont++;t=a[i-1];}
                }
                i++;
            }
            if(cont<=m)
                break;//遇到合适的跳出循环输出
        }
        printf("%d\n",j);
    }
    return 0;
}

杭电 4004 The Frog's Games,布布扣,bubuko.com

杭电 4004 The Frog's Games

原文：http://blog.csdn.net/hanhai768/article/details/23620633