sorry for my bad english :<<
Given an array F of size n (n<=1e5) and a fixed k (k<=n-2). Perform the deletion of k elements, then arrange the elements in ascending order, calling W is the greatest minus between two consecutive elements.
Find the smallest W
input
5 1
4 1 2 3 9
output
1
UPDATE: Solution founded
https://www.geeksforgeeks.org/minimize-the-maximum-difference-between-adjacent-elements-in-an-array/
Auto comment: topic has been updated by duonggsimp (previous revision, new revision, compare).
Auto comment: topic has been updated by duonggsimp (previous revision, new revision, compare).
Sort $$$F$$$.
You have $$$f_1 ≤ f_2 ≤ f_3 ... ≤ f_n$$$. Our answer would be any one of the subarray of $$$F$$$ with $$$n - k$$$ elements.
You can use a multiset
std::multiset<int32_t>in C++ to store the consecutive difference. Just insert and erase for the differences as you traverse. For every subarray, the answer would be the first element of the multiset as it is sorted by default. You can do*multiset.begin()to get the answer.