一些村庄建在一条笔直的高速公路边上。我们用一条坐标轴来描述这条高速公路,每一个村庄的坐标都是整数,没有两个村庄坐标相同。两个村庄间的距离,定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局――当然,并不是每一个村庄都必须建立邮局,邮局必须被建在村庄里,因此它的坐标和它所在村庄坐标相同。每个村庄使用离它最近的那个邮局,建立这些邮局的原则是:所有村庄到各自所使用的邮局的距离总和最小。
你的任务是编写一个程序,在给了每个村庄的坐标和将要建立的邮局数之后,按照上述原则,合理地选择这些邮局的位置。
输入文件的第一行有2个正整数:村庄数V(V<=300),邮局数P(P<=30),P<=V。
第二行有N个正整数,分别代表N个村庄的坐标。坐标的范围是[1,10000],坐标按递增顺序给出。
输出一行一个正整数S,即所有村庄到最近邮局的距离总和的最小可能值。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15