1 人解决，2 人已尝试。
1 份提交通过，共有 10 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
After a new administrative division of Byteland cartographic office works on a new demographic map of the country. Because of technical reasons only a few colors can be used. The map should be colored so that regions with the same or similar population (number of inhabitants) have the same color. For a given color k let A(k) be the number, such that:
at least half of regions with color k has population not greater than A(k)
at least half of regions with color k has population not less than A(k)
A coloring error of a region is an absolute value of the difference between A(k) and the region’s population. A cumulative error is a sum of coloring errors of all regions. We are looking for an optimal coloring of the map (the one with the minimal cumulative error).
Write a program which:
1.reads the population of regions in Byteland ,
2.computes the minimal cumulative error,
3.writes the result.
In the first line of the input an integer n is written, which is the number of regions in Byteland, 10< n <3000. In the second line the number m denoting the number of colors used to color the map is written, 2 <= m <= 10. In each of the following n lines there is one non-negative integer - a population of one of the regions of Byteland. No population exceeds 2^30.
Your program should write in the only line of the output one integer number equal to a minimal cumulative error, which can be achieved while the map is colored (optimally).
11 3 21 14 6 18 10 2 15 12 3 2 2
15
1 人解决，2 人已尝试。
1 份提交通过，共有 10 份提交。
9.9 EMB 奖励。