华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1191|回复: 0
打印 上一主题 下一主题

P4767 [IOI2000]邮局

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-9-28 16:42:20 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P4767


题目描述
高速公路旁边有一些村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入输出格式
输入格式:
第一行包含两个整数:第一个是村庄V的数量,第二个是邮局的数量P,P≤V≤3000.

第二行包含V个整数。这些整数是村庄的位置。对于每个位置XX,认为1≤X≤10000。

输出格式:
第一行包含一个整数S,它是每个村庄与其最近的邮局之间的所有距离的总和。

输入输出样例
输入样例#1:
10 5
1 2 3 6 7 9 11 22 44 50
输出样例#1:
9
说明
对于40%的数据,V≤300
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 03:08 , Processed in 0.550805 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表