网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[IOI2000]邮局
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | postoffice.in | 输出文件 | postoffice.out |
【题目描述】
有一条笔直的高速公路,路旁分布着一些村庄。公路可以用一条数轴表示,则村庄的位置就是其坐标。没有两个村庄的坐标相同。两个村庄之间的距离就是它们坐标之差的绝对值。
一些——但不一定是所有的村庄将修建邮局。邮局和该邮局所在的村庄处于同一位置。应当仔细选择邮局的位置,使得所有村庄到最近邮局的距离总和最短。
你要编写一个程序,给出所有村庄的坐标和计划修建的邮局个数,计算所有村庄到最近邮局的距离总和的最小可能值。
【输入格式】
输入文件的第一行有2个正整数:村庄数V(1<=V<=300),邮局数P(1<=P<=30),P<=V。
第二行有V个正整数,分别代表N个村庄的坐标。坐标的范围是[1,10000],坐标按递增顺序给出。
【输出格式】
输出一行一个正整数S,即所有村庄到最近邮局的距离总和的最小可能值。
【样例输入】
10 5
1 2 3 6 7 9 11 22 44 50
【样例输出】
9
【提示】
对于30%的数据,1<=P<=N<=10.
对于100%的数据,1<=P<=30,1<=N<=300,P<=N.