Min abs difference of K points in an array.

Правка en2, от Diksha_goyal, 2021-11-05 12:55:28

Given an array ~~~~~ A ~~~~~

of size n i.e., ~~~~~ A = {A_1, A_2, ... A_n} ~~~~~

you are given ~~~~~ K ~~~~~

. you can choose any ~~~~~ K ~~~~~

integers (not necessarily from the given array)

i.e, X_1, X_2, X_3 .... X_K

Now, we define a function ~~~~~ F ~~~~~

for each A_i, such that ~~~~~ F_i = min(abs(A_i — X_j)) ~~~~~

 where 1<= j <=K.

find the minimum value of ~~~~~ F_1 + F_2 + .... F_n. ~~~~~

constraints:

1 <= n <= 10^5
1<= K <= n
Теги sorting, array, number theory, median, algorithms, optimization, maths

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Diksha_goyal 2021-11-05 13:27:31 8 Tiny change: 'n(abs(A_i &mdash; X_j)) whe' -> 'n(abs(A_i - X_j)) whe'
en6 Английский Diksha_goyal 2021-11-05 12:57:20 36
en5 Английский Diksha_goyal 2021-11-05 12:56:27 20
en4 Английский Diksha_goyal 2021-11-05 12:56:08 0 Reverted to en1
en3 Английский Diksha_goyal 2021-11-05 12:55:47 196 Reverted to en1
en2 Английский Diksha_goyal 2021-11-05 12:55:28 196
en1 Английский Diksha_goyal 2021-11-05 12:53:37 424 Initial revision (published)