luogu#P5929. [POI1999] 地图
[POI1999] 地图
题目背景
一个人口统计办公室要绘制一张地图。
题目描述
由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色 ,则 是相应的数,则有:
- 在用颜色的区域中至少有一半的区域的人口不大于 。
- 在用颜色的区域中至少有一半的区域的人口不小于 。
区域颜色误差是该区域的人口与 差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案,使得累计误差最小。
输入格式
第一行有一个整数 ,表示区域数。
在第二行中的数 表示颜色数。
在接下来的 行中每行有一个非负整数,表示一个区域的人口。
人口都不超过 。
输出格式
输出一个整数,表示最小的累计误差。
11
3
21
14
6
18
10
2
15
12
3
2
2
15
提示
对于 的数据,,。