问题1225--快餐店

1225: 快餐店

时间限制: 1 Sec  内存限制: 128 MB
提交: 137  解决: 83
[提交] [状态] [讨论版] [命题人:]

题目描述

排成一条直线的公路上有N个加油站,为了方便加油站的员工吃饭,需要在这N个加油站点位置选K个开设快餐店。那么问题来了,怎样选取能使得每个加油站都可以就近吃饭。所谓的就近吃饭,就是每个加油站的人员会去最近的快餐店吃饭,需要走两个加油站之间的距离。我们的目标是让每个加油站到最近快餐店的距离之和最小(具体可以看样例解释)。

输入

输入N, K

然后接下来N行,每行输入一个整数ai,表示加油站的位置(这个位置的值是递增的)

输出

输出最小的距离之和,格式见样例输出

样例输入 Copy

6 3
5
6
12
19
20
27

样例输出 Copy

Total distance sum = 8

提示

【样例说明】

选择第246站点作为快餐店,那么前三个站点人会去第一个快餐店,45站点人回去第二个快餐店,剩下的第三个快餐店。距离之和为:

(1+0+6)+(0+1)+0=8

【数据规模和约定】

1<=N<=200  1<=K<=30  K<=N   1<=ai<=100000

来源/分类