二分法
不斷枚舉一個(gè)值，然后根據(jù)題目要求判斷，這個(gè)值與正確答案的大小關(guān)系，修改上下界的值，
無窮逼近正確答案，最后就是正確答案
其實(shí)我還沒有真正了解，通過別人的代碼去做的。。。
1
#include <cstdio>
2#include <algorithm>
3
4const int SIZE = 50002 ;
5
6int length , N , M ;
7int distance[SIZE] ;
8
9bool Judge(const int& value)
10
{
11
int num , i , pre ;
12 num = 0 ;
13 pre = 0 ;
14
15 for ( i = 0 ; i < N ; ++i )
16
{
17 if ( distance[i] - pre < value )
18 num++ ;
19 else
20 pre = distance[i] ;
21
}
22
23 if ( length - pre < value )
24 num++ ;
25
26 if ( num <= M )
27 return true ;
28 else
29 return false ;
30
31
32
}
33
34int BiSearch()
35{
36 int ans = 0 ;
37 int mid , left = 0 , right = length ;
38
39 while ( left <= right )
40 {
41 mid = (left + right) >> 1 ;
42
43 if ( Judge(mid) )
44 left = mid + 1 ;
45 else
46 right = mid - 1 ;
47 }
48
49 ans = left - 1 ;
50
51 return ans ;
52}
53
54int main()
55{
56// freopen("1.txt", "r", stdin) ;
57
58 int i ;
59 char strNum[12] ;
60
61 scanf("%d %d %d", &length, &N, &M) ;
62
63 getchar() ;
64 for ( i = 0 ; i < N ; ++i )
65 {
66 // scanf("%d", &distance[i]) ;
67 gets(strNum) ;
68 distance[i] = atoi(strNum) ;
69 }
70
71 std::sort(distance, distance + N) ;
72
73 printf("%d\n", BiSearch()) ;
74
75 return 0 ;
76}