邮局

题目内容

题目描述

一些村庄建在一条笔直的高速公路边上。我们用一条坐标轴来描述这条高速公路,每一个村庄的坐标都是整数,没有两个村庄坐标相同。两个村庄间的距离,定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局――当然,并不是每一个村庄都必须建立邮局,邮局必须被建在村庄里,因此它的坐标和它所在村庄坐标相同。每个村庄使用离它最近的那个邮局,建立这些邮局的原则是:所有村庄到各自所使用的邮局的距离总和最小。

你的任务是编写一个程序,在给了每个村庄的坐标和将要建立的邮局数之后,按照上述原则,合理地选择这些邮局的位置。

输入描述

输入文件的第一行有2个正整数:村庄数V(V<=300),邮局数P(P<=30),P<=V。

第二行有N个正整数,分别代表N个村庄的坐标。坐标的范围是[1,10000],坐标按递增顺序给出。 

输出描述

输出一行一个正整数S,即所有村庄到最近邮局的距离总和的最小可能值。

样例输入

10 5 1 2 3 6 7 9 11 22 44 50

样例输出

9

提示

提交评测
请登录后再操作

题目描述

邮局
1103
0
Level2
122
79
65%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在