Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 12thIOI第二天试题一
发信站: 哈工大紫丁香 (2001年06月14日15:38:00 星期四), 站内信件

Post Office
PROBLEM
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 identi
fied 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 intege
r 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 d
istances 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 bet
ween each village and its nearest post office, and the respective desired pos
itions of the post
offices.
INPUT
The input file name is POST.IN. The first line contains two integers: the fir
st is the number of villages V, 1￡V￡300, and the second is the number of po
st offices P, 1￡P￡30, P￡V. The second line contains V integers in increasi
ng order. These V
integers are the positions of the villages. For each position X it holds that
 1￡X￡10000.
OUTPUT
The output file name is POST.OUT. The first line contains one integer S, whic
h is the sum of all distances between each village and its nearest post offic
e as reported in the second line. The second line contains P integers in incr
easing order. These
integers are the locations of the distinct villages in which the post offices
 will be built. There may be several different solutions for the locations, a
nd your program needs to output only one of them.
EXAMPLE INPUT AND OUTPUT
POST.IN                                         POST.OUT
PARTIAL CREDIT
If your program's output does not satisfy the output requirements, then your
score is 0. Otherwise, your score will be computed based on Table 1 as follow
s. If your program outputs sum S and the actual least possible sum is Smin, t
hen calculate
q=S/Smin and find your score c in the bottom row.
 q=S/Smin       q=1.0   1.0<q￡1.1      1.1<q￡1.15     1.15<q￡1.2     1.2<q
￡1.25     1.25<q￡1.3     1.3<q
c       10      5       4       3       2       1       0
Table 1.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]