6933: BZOJ2933:[Poi1999]地图

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

  一个人口统计办公室要绘制一张地图。由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: