专业电子网站建设,平面广告怎么做,繁昌县网站开发,seo排名系统源码题干#xff1a;
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在一张2D地图上有N座城市#xff0c;坐标依次是(X1, Y1), (X2, Y2), ... (XN, YN)。
现在H国要修建一条平行于X轴的天然气主管道。这条管道非常长#xff0c;可以认为是一条平行于X轴的直线。…题干
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在一张2D地图上有N座城市坐标依次是(X1, Y1), (X2, Y2), ... (XN, YN)。
现在H国要修建一条平行于X轴的天然气主管道。这条管道非常长可以认为是一条平行于X轴的直线。
小Ho想知道如何修建这条管道可以使N座城市到管道的垂直距离之和最小。请你求出这个最小的距离之和。
输入
第一行包含一个整数N。
以下N行每行包含两个整数Xi, Yi。
1 N 100000
0 Xi, Yi 1000000
输出
一个整数代表最小的距离之和。
样例输入
4
0 0
0 100
100 0
100 100
样例输出
200
解题报告 直接暴力肯定会T的。 |x-a| |x-b| |x-c| ...是个三节棍不难证明对于多个距离之和是个n节棍忽然想起来高中老师也讲过这个貌似。 而且如果n是偶数的话取中间两个点答案应该是一样的。 如果是可以有小数的话大概就退火了吧然而这数据范围大概是不允许的
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
const int INF 0x3f3f3f3f;
int x[MAX],y[MAX];
int main()
{int n;int minn INF,maxx -INF;cinn;for(int i 1; in; i) {scanf(%d%d,x[i],y[i]);}sort(y1,yn1);ll ans1 y[n/2],cal10;ll ans2 y[n/21],cal20;for(int i 1; in; i) {cal1 abs(ans1 - y[i]);cal2 abs(ans2 - y[i]);}printf(%lld\n,min(cal1,cal2));return 0 ;}
