I’m having some trouble on this problem: CSES - Food Division
The solution turns out to be the following:
- Calculate the amount of food each person needs, positive or negative.
- Calculate the prefix sum of the above array.
- Sort the above prefix sum array.
- Find the median of the sorted prefix sum array.
- Sum up all the absolute value difference between each prefix sum and the median. This is the answer.
However I cannot understand why this produces correct answer. I know that to get a list of numbers equal in minimum steps, all the numbers need to move to the median. But I don’t understand how is it to do with the prefix sum, and how is prefix sum related to the circular array in the problem.