2016 Al-Baath University Training Camp Contest-1 I. March Rain —

题目链接：http://codeforces.com/problemset/gymProblem/101028/I

I. March Rain

time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

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?

Input

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).

Output

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.

Example

input

3

5 2

1 2 3 4 5

7 3

1 3 8 9 10 14 17

5 3

1 2 3 4 20

output

Note

In the second test case the roof looks like this before and after putting the strips.

题解：

一开始以为是区间覆盖问题。后来想到可以用二分来寻找答案。由于付款金额依照最长长条的长度。所以就把每条长条都想成是最长的。二分长度，然后判断当前长度是否能覆盖完所有漏洞。

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<map>

 #include<string>

 #include<set>

 using namespace std;

 #define pb push_back

 #define ms(a, b) memset(a,b,sizeof(a));

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = ;

 int a[], T, n,k;

 int test(int len)

 {

     int now= , cnt = ;

     for(int i = ; i<n; i++)

     {

         if(a[i]>now)

         {

             cnt++;

             now = a[i]+len-;

             if(cnt==k)//如果用完了k条时，判断是否已经覆盖完

             {

                 if(now>=a[n-])

                     return ;

                 else

                     return ;

             }

             if(now>=a[n-])//如果没用完k条，就覆盖完的话，肯定可以

                 return ;

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         for(int i = ; i<n; i++)

         {

             scanf("%d",&a[i]);

         }

         int h = , t = a[n-];

         while(t%k) t++;//注意这一步，将t自加到能整除k为止

         int mid;

         while(h<=t)

         {

             mid = (h+t)/;

             if(test(mid))

                 t = mid-;

             else

                 h = mid+;

         }

         printf("%d\n",h);

     }

     return ;

 }

巴特西

2016 Al-Baath University Training Camp Contest-1 I. March Rain —— 二分

最新文章

热门文章