BZPRO
#2933. [Poi1999]地图
内存限制：128 MiB
时间限制：1 Sec
提交
提交记录
讨论
题目描述
一个人口统计办公室要绘制一张地图。由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色
k
，则
A
(
k
) 是相应的数，则有：
在用颜色k的区域中至少有一半的区域的人口不大于
A
(
k
)
在用颜色k的区域中至少有一半的区域的人口不小于
A
(
k
)
区域颜色误差
是该区域的人口与
A
(
k
)差的绝对值。
累计误差
是所有区域颜色误差的总和。我们要求出一种最佳的染色方案（累计误差最小）。
任务
写一个程序：
读入每个区域的人口数
计算最小的累计误差
将结果输出
输入格式
第一行有一个整数
n
，表示区域数，
10< n <3000
。在第二行中的数
m
表示颜色数，
2 <= m <= 10
。在接下来的
n
中每行有一个非负整数，表示一个区域的人口。人口都不超过
2^30
。
输出格式
输出一个整数，表示最小的累计误差
样例
样例输入
11
3
21
14
6
18
10
2
15
12
3
2
2
样例输出
15
数据范围与提示
BZPRO