网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[POI]地图着色
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 10:25 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 10:25 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 10:25 |
输入文件 | dtzs.in | 输出文件 | dtzs.out |
在Byteland新的行政划分以后,制图工作室需要制作国家新的统计地图。因为技术上的原因,仅有很少的颜色能够被使用。地图上有着相同或者相似的人口(居民数)的地区被着为相同的颜色。对于给定的颜色K,让A(k)为数字,意思为:
- 至少有一半颜色为k的地区人口不大于A(k)。
- 至少有一半颜色为k的地区人口不少于A(k)。
地区的着色误差是指A(k)与地区人口之间的差额的绝对值,累积误差是指所有地区的着色误差之和。我们寻找一种地图的最佳着色方案(即最小的累积误差)
任务
写一个程序:
- 从输入文件读取Byteland地区的人口,
- 计算最小的累积误差,
- 把结果写到文件中。
输入
在输入文件的首行有一个整数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