7329. Construction

After finishing his chalet construction, Stepan still has n wooden boards, with lengths l₁, ..., l_n. He decided to build a fishing deck on a lake using these boards.

Stepan believes that the longer deck is, the more fish he will catch!

Moreover, Stepan, as all fishermen, is very superstitious and trusts all omens. One of it – the deck can be build using whole boards only (boards can be cut but not joined). Now Stepan is interested what maximum deck length d can be obtained, if needs to use m boards.

Input. Contains integers n, m, l_i (1 ≤ n ≤ 10000, 1 ≤ m, l_i ≤ 2 * 10⁹) – number of available boards, number of boards to be used to build the deck and the lengths of available boards.

Output. Print one integer d – the maximum possible length of the deck or 0 (zero).

Sample input	Sample output
4 6 16 12 20 10	8

SOLUTION

binary search

Algorithm analysis

Let’s find the length of the deck d with binary search. Initially let d Î [Left; Right] = [0; INF]. Consider the next subtask: is it possible to construct the required bridge with length exactly Mid = (Left + Right) / 2 ? To do this, count how many boards of length Mid we can get. From the board of length l_i we can get such boards. By cutting you can get

boards of length Mid. If in total we can get m boards, set Left = Mid + 1. Otherwise set Right = Mid. The answer will be the value of Left – 1.

Example

In the given sample there are 4 boards. It is necessary to build a deck with 6 boards.

If the length of the deck will be 8, then the existing boards can be cut as follows, getting 16/8 + 12/8 + 20/8 + 10/8 = 6 boards of length 8.

If the length of the deck will be 9, then we can get only 16/9 + 12/9 + 20/9 + 10/9 = 5 boards of length 9, which is less than the required 6.

Algorithm realization

Define the constants. The lengths of the boards l_i store in array a.

#define INF 2000000010

#define MAX 1000009

long long a[MAX];

Function cnt returns the number of boards that can be cut from available with lengths equal to Mid. This value equals to the sum .

long long cnt(long long Mid)

{

if (Mid == 0) return INF;

long long res = 0;

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

res += a[i] / Mid;

return res;

}

The main part of the program. Read the input data.

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

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

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

Set the boundaries for value d Î [Left; Right] = [0; INF] and run a binary search.

Left = 0;

Right = INF;

while (Left < Right)

{

Mid = (Left + Right) / 2;

The cnt(Mid) value is equal to the number of boards that can be cut from the existing ones, provided that their lengths are equal to Mid. If this number is less than the required value of m, then the length of the deck should be decreased by setting Right = Mid. Otherwise, move the left end Left.

if (cnt(Mid) < m) Right = Mid;

else Left = Mid + 1;

}

Print the answer.

printf("%lld\n",Left - 1);