Chocolate Distribution
mediumPlacement Coding+20 XPTime limit 2s
There are n packets of chocolates; packet i has a[i] chocolates. Give exactly one packet to each of m students so that the difference between the largest and smallest packet given out is as small as possible. Print that smallest difference.
Input:
- line 1:
n m - line 2:
nintegers
Output: the minimum possible difference.
Constraints: 1 ≤ m ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 10⁹.
Think about it: after sorting, the best choice is always m packets that sit next to each other. Slide a window of size m and take the smallest a[i + m − 1] − a[i].
Sample input 1
8 5 3 4 1 9 56 7 9 12
Sample output 1
6
Sample input 2
7 3 7 3 2 4 9 12 56
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).