2170: 宝典2第十一章邮局问题

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

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

【输入格式】

共两行，第一行给出村庄数目V和邮局数目P，1≤V≤300，1≤P≤30，P≤V，第二行按递增顺序给出V个村庄的坐标x₁，x₂，…，x_V，1≤x_i≤10000。

【输出格式】

输出Ｐ个以空格分隔的整数，按坐标从小到的顺序给出Ｐ个邮局的坐标。

【输入样例】

10 5

1 2 3 6 7 9 11 22 44 50

【输出样例】

９