Greedy or DP? Please help me out!!

Revision en1, by lol_py, 2022-08-19 22:18:23

You are given an array A of integers, you have to choose two integers x, y such that summation min(abs(A[i] — x), abs(A[i] — y)) for each i in 1 to N is minimised.

e.g:

A = [1, 2, 6, 7]

x = 1, y = 7

(1 — 1) + (2 — 1) + (6 — 7) + (7 — 7) = 2

2 <= N < 10^3

I tried to solve this greedily but got WA.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lol_py 2022-08-19 22:18:23 388 (published)