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.Tysm
english con cac
hellnah
I have an idea, since you have found the solution, can you tell me if I am thinking in the right direction?
I observed that it is optimal to delete elements only from prefix and suffix. We sort the array, then binary search on W. For a given w, we find the length of the longest sub-array(let's say l, r) such that the consecutive difference is atmost w (using two-pointer). Then the elements deleted would be n — (r-l+1). Now, if this is <=k then we can try to increase w and delete more elements otherwise decrease w.
oh thanks
It was a question bro. Am I thinking in the right direction?
u can get me ur code abt this problem and i will check it 4 u ;)
he 's just a kid kid watching skibidi dop dop yes yes. Confusing between question and answer mean he didn't actually care about your comment so don't give a fck to him.