Description
It is raining again! Youssef really forgot that there is a chance of rain in March, so he didn't fix the roof of his house. Youssef's roof is 1-D, and it contains n holes that make the water flow into the house, the position of hole i is denoted as xi where (0 ≤ i < n). Youssef has to put strips at the bottoms of those holes in order to prevent the water from flowing. Let's say there is a hole in position 4 and another hole in position 6, and Youssef decided to use a strip of length 3 to cover those two holes, then he places the strip from position 4 to 6 (it covers positions 4,5,6) and it covers the two holes. He can buy exactly k strips, and he must pay a price equal to the longest strip he buys. What is the minimum length l he can choose as the longest strip in order to keep his house safe?
The input consists of several test cases. The first line of the input contains a single integer T, the number of the test cases. Each test case consists of two lines: the first line contains two space-separated integers, n and k (1 ≤ k < n ≤ 100000), denoting the number of the holes in the roof, and the number of the strips he can buy respectively. The second line of the test case contains n integers (x0, x1, ..., xn - 1): (0 ≤ xi ≤ 109), denoting the positions of holes (these numbers are given in an increasing order).
For each test case print a single line containing a single integer denoting the minimum length l he can choose in order to buy k strips (the longest of them is of length l) and cover all the holes in his house using them.
3
5 2
1 2 3 4 5
7 3
1 3 8 9 10 14 17
5 3
1 2 3 4 20
3
4
2
In the second test case the roof looks like this before and after putting the strips.
题意：屋顶漏水，现在知道xi处是漏的，可以使用k块布盖住，问最短布的长度为多少
解法：二分，首先当然是最大的数字/k，得到最长的长度，然后二分判断
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[100005];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int l=0,r=a[n-1]/m+1;
while(l<=r){
int mid=(l+r)/2;
int x=a[0]+mid-1,cnt=1;
for(int i=0;i<n;i++){
if(a[i]>x){
cnt++;
x=a[i]+mid-1;
}
}
if(cnt<=m){
r=mid-1;
}else{
l=mid+1;
}
}
printf("%d\n",r+1);
}
}