【分治法】输油管道问题

简介: 【分治法】输油管道问题

 问题描述:

问题描述:

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

编程任务:

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

数据输入:

  由文件input.txt 提供输入数据。文件的第1 行是油井数n,1<=n10000。接下来n 行是油井的位置,每行2 个整数x 和y,-10000<=x,y<=10000 。

结果输出:

  程序运行结束时,将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到主管道之间的输油管道最小长度总和。

输入文件示例       输出文件示例

input.txt           output.txt

5                       6

1 2

2 2

1 3

3 -2

3 3

代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
#define N 10000
bool cmp(int a,int b){
    return a<b;
}
int main()
{
    int n;cin>>n;
    int X=0, Y=0;//(X,Y)记录邮局位置
    int MinDis=0;
    int x[N],y[N];
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x,x+n,cmp);
    sort(y,y+n,cmp);
    X=x[n/2];Y=y[n/2];//邮局位置找法思想,两边之和大于第三边
    //将坐标两两分组,距离两点最近距离肯定在其两点间连线上,取交集即可;
    for(int i=0;i<n;i++){
        int dis1=x[i]-X;int dis2=y[i]-Y;
        if(dis1<0) dis1=-1*dis1;
        if(dis2<0) dis2=-1*dis2;
        MinDis=MinDis+dis2;
    //只需要y坐标距离差的绝对值(与邮局选址问题不同,此题为东西走向管道,不需考虑X坐标) 
    }
    cout<<MinDis<<endl;
    return 0;
}

image.gif


目录
相关文章
|
机器学习/深度学习 算法 数据挖掘
【数据挖掘】决策树归纳中ID3算法讲解及构建决策树实战(图文解释 超详细)
【数据挖掘】决策树归纳中ID3算法讲解及构建决策树实战(图文解释 超详细)
877 0
|
存储 缓存 Oracle
Oracle JDBC 驱动程序
开始使用 Oracle JDBC 驱动程序 (Doc ID 1602866.1
2334 0
|
6月前
|
人工智能 自动驾驶 安全
什么是AGI
通用人工智能(AGI)指具备或超越人类智能的机器系统,能跨领域学习、推理和解决问题。其核心特点包括跨领域能力、自主学习与推理、类人思维模式及自适应性。目前AGI仍处早期阶段,但大模型和多模态技术正推动其从理论走向应用,如自动驾驶、科学研究和工业自动化等。尽管前景广阔,AGI仍面临技术瓶颈、伦理安全和资源需求等挑战。未来,AGI有望重塑产业和社会生活方式。
4005 2
|
11月前
|
计算机视觉 Python
Jetson 学习笔记(十):Picamera或者Jetcam打开树莓派CSI摄像头
本文介绍了在Jetson Nano上使用picamera和jetcam库打开树莓派CSI摄像头的方法。由于使用opencv获取CSI摄像头图像延迟高,作者推荐使用picamera,能达到20-30fps。文章提供了安装步骤、基础代码示例,并记录了一些有用的博客地址。
227 2
|
11月前
|
算法 搜索推荐 数据挖掘
二分查找法的应用场景
【10月更文挑战第9天】
633 58
|
11月前
|
数据采集 Web App开发 JavaScript
Selenium爬虫技术:如何模拟鼠标悬停抓取动态内容
本文介绍了如何使用Selenium爬虫技术抓取抖音评论,通过模拟鼠标悬停操作和结合代理IP、Cookie及User-Agent设置,有效应对动态内容加载和反爬机制。代码示例展示了具体实现步骤,帮助读者掌握这一实用技能。
495 0
Selenium爬虫技术:如何模拟鼠标悬停抓取动态内容
|
安全 Java 数据库连接
Java中的异常处理:深入理解try-with-resources语句
在Java的异常处理领域,try-with-resources语句是一个重要的特性,它简化了资源管理并提高了代码的可读性。本文将详细探讨try-with-resources的工作原理、使用场景以及如何正确运用这一结构来优化资源管理,同时指出常见的误用情况和最佳实践。
380 0
|
数据安全/隐私保护
金盾金狮pbb爱问云点盾云加密视频录屏翻录提取教程
此软件专为录制加密网络课程视频设计,能轻松录制通常因加密而无法显示或录制的视频内容,并且录制过程隐蔽不被检测,输出文件为通用MP4格式。使用步骤简易:首先播放视频,然后打开软件并登录,即可开始录制。
2037 18
|
Java
Java实现简易计算器
Java实现简易计算器
675 5
|
Shell Python
使用Python IDLE进行Debug调试
使用Python IDLE进行Debug调试
264 3