洛谷P1862输油管道问题

二话不说先上代码：

#include<bits/stdc++.h>

using namespace std;

int n;

int x,y[10001];

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d %d",&x,&y[i]);

	}

	sort(y+1,y+n+1);

	int mid;

	if(n%2==0){

		mid=(y[n/2]+y[n/2+1])/2;

	}else

	{

		mid=y[n/2+1];

	}

	int sum=0;

	for(int i=1;i<=n;i++){

		sum+=abs(y[i]-mid);

	}

	cout<<sum<<endl;

	return 0;

}

思路&证明

这个题超简单啊……哈哈，不过我看题解区竟然有用模拟退火的的大佬？？orzorz，蒟蒻只好在自己的地盘发一个题解……

本题主要思路是中位数。啊没错就是把所有y坐标给他排个序然后求中位数就完事了！

为什么这是对的呢？为什么是中位数而不是平均数呢？

首先我们要明确一件事：x坐标完全没有用。因为我们的主输油管道可以无限长。

接下来对y坐标下手，我们发现，题意可以翻译为：对一个有限的序列，求一个值使得这个值与序列中各值的差的绝对值的和最小。

这不就是中位数吗？？？

至于这个的具体证明，推荐一篇博文：中位数定理

所以直接求中位数就好了呀！

巴特西

洛谷P1862输油管道问题

二话不说先上代码：

思路&证明

最新文章

热门文章