duonggsimp's blog

help me this ST problem
By duonggsimp, history, 19 months ago, In English

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/

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
17 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply