Vijos / 题库 / 输油管道问题

背景

想念car的GF,car就出了道水题!

描述

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?

编程任务:  给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和.

格式

输入格式

输入第1行是油井数n,1≤n≤10000。

接下来n行是油井的位置,每行2个整数x和y,-10000≤x,y≤10000。

输出格式

输出第1行中的数是油井到主管道之间的输油管道最小长度总和。

样例1

样例输入1

5
1 2
2 2
1 3 
3 -2
3 3

样例输出1

6

限制

各个测试点1s

提示

各个测试点1s

来源

经典算法

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 using namespace std;
 5 int a[10001];
 6 int b[10001];
 7 int tot;
 8 int main()
 9 {
10     int n;
11     cin>>n;
12     for(int i=1;i<=n;i++)
13     {
14         cin>>a[i]>>b[i];
15     }
16     sort(b+1,b+n+1);
17     int mid=b[n/2+1];
18     for(int i=1;i<=n;i++)
19     {
20         tot=tot+abs(b[i]-mid);
21     }
22     cout<<tot;
23     return 0;
24 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

干货 | PyTorch相比TensorFlow,存在哪些自身优势?

1、 PyTorch 课替代NumPy 使用:PyTorch 本身主要构件是张量——和 NumPy 看起来差不多。使得 PyTorch 可支持大量相同的 API...

1.7K40
来自专栏DannyHoo的专栏

iOS开发中使用算法之冒泡法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

11930
来自专栏炉边夜话

考场安排---图的着色原理之运用

试设计一算法,当给定一个图时G=(V,E),|V|=n,(Vi,Vj)ЄE,当且仅当有一个同学选了课程i和课程j,试给出一个考试安排方案N1,N2,N3…Nk,...

15910
来自专栏null的专栏

优化算法——遗传算法

与遗传算法的第一次接触 遗传算法是我进入研究生阶段接触的第一个智能算法,从刚开始接触,到后来具体去研究,再到后来利用遗传算法完成了水利水电的程序设计比赛,整个过...

2.1K60
来自专栏freesan44

python 算法开发笔记

19320
来自专栏蜉蝣禅修之道

优化后的Levensthein distance算法实现

40350
来自专栏null的专栏

数据结构和算法——用动态规划求解最短路径问题

一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

48950
来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

70360
来自专栏hadoop学习笔记

HanLP 关键词提取算法分析详解

l 参考论文:《TextRank: Bringing Order into Texts》

18460
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

41120

扫码关注云+社区

领取腾讯云代金券