http://acm.hdu.edu.cn/showproblem.php?pid=4004
Problem Description
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
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
Sample Input
6 1 2
2
25 3 3
11
2
18
Sample Output
4
11
Question meaning:< /p>
The Frog Kingdom Games has begun. The most popular game is the Iron Frog Triathlon, one of which is the jumping across the river. This project requires frog athletes to cross the river by jumping. The width of the river is L. There are n stones arranged in a straight line on the river. Frogs can use these stones to jump across the river, and fail if they fall into the river. The maximum number of frogs can jump is m. Now I want to know how long the frogs need to jump at least to be able to successfully complete the game.
Idea:
Use dichotomy to find the maximum distance of a single jump to see if it can be completed with this distance. Until the smallest number is found, the upper boundary of the bisection is the river width L.
The code is as follows:
1 #include
2 #include <string.h>
3 #include
4 #include <string>
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include <set>
11 #include
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).
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 a ppear in one place is impossible.
For each case, output a integer standing for the frog’s ability at least they should have.
6 1 2
2
25 3 3
11
2
18
4
11
1 #includeFinally jump on the river bank
2 #include <string.h>
3 #include
4 #include <string>
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include <set>
11 #include
32 sort(a+1,a+1+n+1);
33 int MAX=0;//The answer cannot be less than the stone difference The maximum value in the, otherwise the two stones must not jump over
34 for(int i=1;i<=n+1;i++< span style="color: #000000;">)
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)//Find the answer in two points
43 {
44 int mid=(l+r)> >1;//Two points The median value of the method (that is, the maximum distance that the initial frog can jump)
45 int num=0;//Record the number of steps skipped
46 for(int i=1;i<=n+1;)< span style="color: #008000;">//Here we use greed, jump as many rocks as possible at a time
47 {
48 int sum=0;//Test the distance to jump to this stone
49 for(int j=i;j<=n+1;j++)
50 {
51 if(sum+b[j]< =mid)//You can continue to jump
52 {
53 sum+=b[j];
54 if(j==n+1)//I jumped to the shore, Take care of it
55 {
56 num++;
57 i=n+2;
58 break;
59 }
60 }
61 else//Cannot continue to jump
62 {
63 num++;//Add 1 to the number of jumps
64 i=j;//Jump from this rock next time
65 break ;
66 }
67 }
68 }
69 if(num>m)
70 l=mid+1;
71 else
72 r=mid-1;
73 }
74 printf("%d ",l);
75 }
76 return 0;
77 }