POJ1723 SOLDIERS 兄弟连

有一个性质：在一个长为n的序列a中找一个数 \(a_k\) 使得 \(\sum\limits_{i=1}^n abs(a_i-a_k)\) 最小，则 \(a_k\) 是a的中位数。

于是在这题里，对于纵坐标直接找中位数，算一遍上面的式子即可。

横坐标稍加处理：先从小到大排序，此时数组的下标就是士兵最后从左到右的顺序。然后还是找中位数。但是每个士兵是从左到右站，而不是在一条直线上。后来想到把每个士兵的横坐标 \(x_i\) 减去i，这样士兵都在一条直线上，再套用上面的式子即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define int long long

const int N=10005;

int n,x[N],y[N],ans;

int labs(int t)

{

	return t>=0?t:-t;

}

signed main()

{

	scanf("%lld",&n);

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

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

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

	for(int i=1;i<=n;++i)x[i]-=i;

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

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

	int mid=n/2+1;

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

		ans+=labs(x[mid]-x[i])+labs(y[mid]-y[i]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

POJ1723 SOLDIERS 兄弟连

最新文章

热门文章