[POI1999]地图着色

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file map.in Output file map.out

在Byteland新的行政划分以后,制图工作室需要制作国家新的统计地图。因为技术上的原因,仅有很少的颜色能够被使用。地图上有着相同或者相似的人口(居民数)的地区被着为相同的颜色。对于给定的颜色K,让A(k)为数字,意思为:

  1. 至少有一半颜色为k的地区人口不大于A(k)。
  2. 至少有一半颜色为k的地区人口不少于A(k)。

地区的着色误差是指A(k)与地区人口之间的差额的绝对值,累积误差是指所有地区的着色误差之和。我们寻找一种地图的最佳着色方案(即最小的累积误差)

任务

写一个程序:

  1. 从输入文件读取Byteland地区的人口,
  2. 计算最小的累积误差,
  3. 把结果写到文件中。

输入

在输入文件的首行有一个整数n(10< n <3000),它是Byteland的地区数。第二行有数字m(2 <= m <= 10),表示用于着色的颜色数。在接下来的n行中的每一行里有一个非负的整数- Byteland一个地区的人口数。注:人口数不超过2^30。

输出

你的程序应该在输出文件单独的一行里写下一个整数—等于能够完成地图最佳着色的最小累积误差。

样例输入  

11
3
21
14
6
18
10
2
15
12
3
2
2

样例输出  

15