http://acm.hdu.edu.cn/showproblem.php?pid=4004
6 1 2 2 25 3 3 11 2 18
4 11
题意：
青蛙王国运动会开始了，最受欢迎的游戏是铁蛙三项赛，其中一项是跳跃过河项目。这个项目需要青蛙运动员通过跳跃过河。河的宽度是L。在河面上有直线排列的n个石头。青蛙可以利用这些石头跳跃过河，如果落入河中则失败。青蛙们能够跳跃的最多次数是m。现在想要知道青蛙们至少需要具备多大的跳跃距离，才能够顺利完成比赛。
思路：
用二分去查找一个单次跳跃的最大距离，看以这个距离能否完成。直到找到最小的那个数，二分的上边界是河水宽 L。
代码如下：
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 //const double PI=acos(-1); 17 #define Bug cout<<"---------------------"<<endl 18 const int maxn=5e5+10; 19 using namespace std; 20 21 int a[maxn];//存放每块石头到开始处的距离 22 int b[maxn];//存放石头之间的差值 23 24 int main() 25 { 26 int L,n,m; 27 while(~scanf("%d %d %d",&L,&n,&m)) 28 { 29 for(int i=1;i<=n;i++) 30 scanf("%d",&a[i]); 31 a[n+1]=L;//最后要跳到河岸上 32 sort(a+1,a+1+n+1); 33 int MAX=0;//答案不可能会小于石头差值中的最大值，否则这两块石头一定跳不过去 34 for(int i=1;i<=n+1;i++) 35 { 36 b[i]=a[i]-a[i-1]; 37 if(b[i]>MAX) 38 MAX=b[i]; 39 } 40 int l=MAX; 41 int r=L; 42 while(l<=r)//二分查找答案 43 { 44 int mid=(l+r)>>1;//二分法的中值（即初始青蛙能跳的最大距离） 45 int num=0;//记录跳的步数 46 for(int i=1;i<=n+1;)//此处用到贪心，一次尽量多跳几个石头 47 { 48 int sum=0;//检验到这个石头需要跳的距离 49 for(int j=i;j<=n+1;j++) 50 { 51 if(sum+b[j]<=mid)//可以继续跳 52 { 53 sum+=b[j]; 54 if(j==n+1)//跳到岸了，处理一下 55 { 56 num++; 57 i=n+2; 58 break; 59 } 60 } 61 else//不可以继续跳 62 { 63 num++;//跳的次数加1 64 i=j;//下一次从这个石头起跳 65 break; 66 } 67 } 68 } 69 if(num>m) 70 l=mid+1; 71 else 72 r=mid-1; 73 } 74 printf("%d\n",l); 75 } 76 return 0; 77 }
HDU-4004 The Frog's Games （分治）
原文：https://www.cnblogs.com/jiamian/p/11707506.html