I am trying to solve this problem for almost a month now but have had no success. Can someone give me a hint (not entire solution) to solve this problem?
Thanks in advance,
Animesh.
I am trying to solve this problem for almost a month now but have had no success. Can someone give me a hint (not entire solution) to solve this problem?
Thanks in advance,
Animesh.
The obvious first step is to sort all the elements because their order doesn’t matter.
Suppose we’ve fixed L and H, let x be the number of elements <= L which are changed to L and x1 be the number of elements > L which are changed to L. Similarly let y be the number of elements >= H which are changed to H and y1 the number of elements < H which are changed to H.
Let dL be the increase in cost if we increase L by 1 and dH be the increase in cost if we decrease H by 1.
dL = x-x1 and dH = y-y1
Try to prove that there has to be an optimial solution where dL == dH.
Thank you for the prompt reply.