邮局问题

成绩 100 开启时间 2016年05月30日 星期一 19:45
折扣 0.8 折扣时间 2016年05月30日 星期一 19:45
允许迟交 是 关闭时间 2016年05月30日 星期一 19:45
输入文件 PostOffice.in 输出文件 PostOffice.out

【题目描述】邮局问题 (PostOffice.cpp/c/pas) PKU 1160

在魔法世界最繁忙的一条高速公路边上有V个村庄，用一条坐标轴来描述这条公路，每个村庄的坐标各不相同，且都是整数。两个村庄间的距离用它们的坐标值差的绝对值表示。现在从这些村庄中选出P个建立邮局，邮局建立在村庄里，每个村庄使用离他最近的那个邮局，求一种建设方法，使得所有村庄到各自所使用的邮局的距离总和最小。

【输入格式】

共两行，第一行给出村庄数目V和邮局数目P，1≤V≤300，1≤P≤30，P≤V，第二行按递增顺序给出V个村庄的坐标x1，x2，…，xV，1≤xi≤10000。

【输出格式】

输出一个值，表示所有村庄到各自所使用的邮局的距离总和的最小值。

【输入样例】

10 5

1 2 3 6 7 9 11 22 44 50

【输出样例】

９