Problem 1343 --算法实现题 2-1 输油管道问题(习题 2-30)

1343: 算法实现题 2-1 输油管道问题(习题 2-30)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $10$ 正确数量 $6$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 递归
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有 n 口油井的油
田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定 n口油
井的位置,即它们的 x 坐标(东西向)和 y 坐标(南北向),应如何确定主管道的最优位置,
即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道
的最优位置。 
«算法设计: 
给定 n 口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。 
第 1 行是油井数 n,1<=n<=10000。接下来 n 行是
油井的位置,每行 2个整数 x和 y,-10000<=x,y<=10000。 
输出第 1 行中的数是油井到主管道之间的输油管道最小长度总和
5
1 2
2 2
1 3
3 -2
3 3
6

推荐代码 查看1343 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 淡意的温柔 591151 2020-06-06 08:50:26
内存最少[$0 $KB] hanlei 503485 2019-10-23 20:25:10
第一AC AOJ大管家 103231 2017-06-06 21:53:11
第一挑战 AOJ大管家 103228 2017-06-06 21:46:27

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛