duonggsimp's blog

help me this ST problem
By duonggsimp, history, 2 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duonggsimp (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duonggsimp (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

english con cac

→ Reply