ACdream 1735 输油管道
2024-10-18 17:06:39
输油管道
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 262144/131072KB (Java/Others)
Problem Description
平面上有n个油井,现在要建立一条主干线,用来把所有的油井产出的原油都输送出去,主干线是平行于x轴的一条直线,每个油井通过一条支线把原油输送到主干线上,现在给定n个油井在平面上的坐标,那么应该把主干线建在什么地方才能让所有的支干线的总长度最小呢?
Input
首先一个正整数n,接下来n行每行两个整数,代表n个油井在平面上的位置。n和坐标都是小于等于1000000的正整数。
Output
输出总的支干线长度的最小值,每个结果占一行。
Sample Input
2
0 0
10 10
Sample Output
10
Source
第九届北京化工大学程序设计竞赛
Manager
解题:中位数的运用
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
typedef long long LL;
LL y[maxn],x;
int main(){
int n;
while(~scanf("%d",&n)){
for(int i = ; i < n; ++i)
scanf("%lld%lld",&x,y+i);
sort(y,y+n);
LL mid = y[(n-)>>],ret = ;
for(int i = ; i < n; ++i)
ret += abs(y[i] - mid);
printf("%lld\n",ret);
}
return ;
}
最新文章
- 【SSM 4】Mybatis逆向生成工具
- Mysql Innodb 间隙锁浅析
- LinckedhashMap原理
- [Stephen]页面实现瀑布流源码
- 【m元素集合的n个元素子集】
- 笔记本电脑连接上WiFi后,弹不出登录界面怎么办?
- Redis集群教程(Redis cluster tutorial)
- 已知两点经纬度(百度地图),用js求解两点之间的角度
- 天融信防火墙NGFW4000,无法进入web管理和community属性查看
- 使用centos 7安装conpot
- SMBv1 is not installed by default in Windows 10 Fall Creators Update 2017 and Windows Server, Semi-annual Channel
- Day5 函数递归,匿名、内置行数,模块和包,开发规范
- :迭代器模式1:Iterator
- swift和oc的protocol的成员变量
- 《剑指offer》— JavaScript(33)丑数
- linux环境中安装ftp服务
- ubuntu下安装软件的三种方法
- Spark入门3(累加器和广播变量)
- js中级系列:模块化(转载 学习中。。。。)
- 初始化mysql数据库时提示字符编码错误的解决办法
热门文章
- CNN tensorflow text classification CNN文本分类的例子
- golang LMDB入门例子——key range查询
- HDU 5692 Snacks(DFS序+线段树)
- Eqs(枚举+ hash)
- bzoj 2599(点分治)
- [Apple开发者帐户帮助]一、开始(2)登录您的开发者帐户
- git clone 出现错误
- php 提交编辑数据没有变,返回0,判断
- Spring Boot (17) 发送邮件
- 5.12redis