洛谷——P1862 输油管道问题
2024-08-24 16:37:51
P1862 输油管道问题
题目背景
听说最近石油危机
所以想到了这题
题目描述
某石油公司计划建造一条由东向西的主要输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。如果给定n口油井的位置,及它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可规定时间内确定主管道的最优位置。
输入输出格式
输入格式:
第一行是油井数n(1<=n<=10000)
接下来n行是油井的位置,每行2个整数x和y(-10000<=x,y<=10000)
输出格式:
只有一行
是油井到主管道之间的输油管道最小长度总和
输入输出样例
输入样例#1: 复制
5 1 2 2 2 1 3 3 -2 3 3
输出样例#1: 复制
6 最有情况为将管道修在所有y的中位数的位置,因为这个题管道是东西的,那么也就是说这个题的x对题目没有影响。然后在for循环求解就好了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 10010 using namespace std; int n,w,ans; int read() { ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } struct Node { int x,y; }node[N]; int cmp(Node a,Node b) { if(a.y!=b.y)return a.y<b.y; else return a.x<b.x; } int main() { n=read(); ;i<=n;i++) node[i].x=read(),node[i].y=read(); sort(node+,node++n,cmp); w=node[n/+].y; ;i<=n;i++) ans+=abs(node[i].y-w); printf("%d",ans); ; }
最新文章
- InetAddress类
- leetcode-Warm Up Contest-Aug.21
- Android内存性能优化(内部资料总结) eoe转载
- PHP中关于 basename、dirname、pathinfo 详解
- WebGIS基础复习笔记
- Using Run-Time Dynamic Linking(使用运行时动态链接库)
- [React] Radium: Updating Button Styles via Props
- php composer使用
- Blacksmith test
- 零成本实现Android/iOS自动化测试:基于Appium和Test Perfect
- url语法
- CRL快速开发框架4.4版发布,支持主从读写分离
- [BZOJ 1500]维修数列 [Splay Tree从进阶到住院]
- hadoop源码import到eclipse工程
- Apache shiro的简单介绍与使用(与spring整合使用)
- app.get is not a function解决方案
- thinkphp5.1验证器场景验证中传参的方法。
- 虚拟机Ubuntu图形界面进入命令行快捷键
- python简说(五)操作文件
- Linux命令学习之路——文档权限管理:chmod