Reading - MarisaOJ: Marisa Online Judge

Marisa has

$n$ books, with the

$i$ -th book located at position

$A_i$ . She wants to select

$k$ books to read. Marisa believes that if she selects two books too close to each other, it will affect the aesthetic value of the books. Therefore, she wants to find a way to choose

$k$ books such that the minimum distance between any two consecutive books selected is as large as possible. For example, if Marisa selects books at positions

$1, 3, 7, 10$ , the minimum distance between any two consecutive books is

$2$ , which is the distance between the books at positions

$1$ and

$3$ . ### Input - The first line contains two integers

$n, k$ . - The second line contains

$n$ integers

$A_i$ . No two books occupy the same position. ### Output - The maximum distance ensuring she can select exactly

$k$ books. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le A_i , k\le 10^9$ . ### Sample Input:

$5 3 10 4 2 3 1$

Output:

$3$

Binary search on answer
	Reading
	Minimum maximum
	Beautiful number
	Multiplication table
	k-th digit
	Maximum mean
	Birthday
	Sorting the differences
	Collecting

Topic

Binary search

Rating

800

Solution (0)

Solution