题意:
每年奶牛们都要举办各种特殊版本的跳房子比赛,包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行,在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间,有N (0 ≤ N ≤ 50,000) 个岩石,每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中,奶牛轮流从起点出发,尝试到达终点,每一步只能从一个岩石跳到另一个岩石。当然,实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移,看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行,他感到非常厌烦。他计划移走一些岩石,使得从起点到终点的过程中,最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后,最长可能的最短跳跃距离是多少?
输入第一行包含三个整数L, N, M,相邻两个整数之间用单个空格隔开。
接下来N行,每行一个整数,表示每个岩石与起点的距离,不会有两个岩石出现在同一个位置。输出一个整数,最长可能的最短跳跃距离。
样例输入
25 5 2 2 14 11 21 17
样例输出
4
思路:
二分。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int l, n, m; 6 const int INF = 0x3f3f3f3f; 7 int a[50005]; 8 bool judge(int x) 9 { 10 int cnt = 0; 11 int front = 1, end = 0; 12 while (front < n) 13 { 14 if (a[front] - a[end] < x) 15 { 16 cnt++; 17 } 18 else 19 { 20 end = front; 21 } 22 front++; 23 } 24 return cnt <= m; 25 } 26 int binary_search(int p) 27 { 28 int l = 1, r = p, m, res = 1; 29 while (l <= r) 30 { 31 m = (l + r) >> 1; 32 if (judge(m)) 33 { 34 res = m; 35 l = m + 1; 36 } 37 else 38 { 39 r = m - 1; 40 } 41 } 42 return res; 43 } 44 int main() 45 { 46 while (cin >> l >> n >> m) 47 { 48 for (int i = 1; i <= n; i++) 49 { 50 scanf("%d", &a[i]); 51 } 52 sort(a + 1, a + n + 1); 53 a[n + 1] = l; 54 n += 2; 55 printf("%d ", binary_search(l)); 56 } 57 return 0; 58 }