Post Office（翻译）

2022.2.10

题目网址：

http://noi.openjudge.cn/ch0206/162/

原题：

Post Office

总时间限制: 

1000ms

内存限制: 

65536kB

描述

There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.

Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.

You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

输入

Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000.

输出

The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.

翻译：

描述：

这里有一条笔直的公路，沿公路旁有乡村。这条公路代表一条整数对称轴，并且每个村庄的位置都有单个的整数坐标。没有两个乡村在同一个位置上。两个位置的距离取决于它们整数坐标的不同值。

邮局将被建在某个位置，但是不是所有的乡村。一个乡村和这个邮局有相同的位置。为了建这个邮局，它们的位置应该被选以便于每个乡村与离它最近的邮局的总距离最小。

你应该写一个程序，这个程序被给了乡村的位置和邮局的数量，计算至少可能的每个乡村与离它最近的邮局的总距离。

输入：

你的程序应该读标准输入。第一行包含两个整数：第一个整数是乡村V的数量，1<=V<=300，第二个是邮局P的数量，1<=P<=30，P<=V。第二行包含V个递增整数。这些V整数是乡村的位置。对于每个位置X都有1<=X<=10000。

输出：

第一行包含1个整数S，是每个乡村与离它最近的邮局之间的距离的总和。