luoguP3964 [TJOI2013]松鼠聚会

链接

思路

切比雪夫距离有max，不好优化。

但是我们能转化成曼哈顿距离，只需要

\((x,y)变成(\frac{x+y}{2},\frac{x-y}{2})\)

相反的曼哈顿距离转切比雪夫距离

\((x,y)=>(x+y,x-y)\)

详情见attack

剩下的就是sort直接做了

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+7;

int n;

struct node {

	int val,id;

	bool operator < (const node &b) const {

		return val<b.val;

	}

}a[N],b[N];

ll ans[N],sum[N][2],mi;

int main() {

	scanf("%d",&n);

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

		scanf("%d%d",&tmpa,&tmpb);

		a[i].val=(tmpa+tmpb),a[i].id=i;

		b[i].val=(tmpa-tmpb),b[i].id=i;

	}

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

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

	for(int i=1;i<=n;++i) sum[i][0]=sum[i-1][0]+a[i].val;

	for(int i=n;i>=1;--i) sum[i][1]=sum[i+1][1]+a[i].val;

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

		ans[a[i].id]+=1LL*a[i].val*(i-1)-sum[i-1][0];

		ans[a[i].id]+=sum[i+1][1]-1LL*(n-i)*a[i].val;

	}

	for(int i=1;i<=n;++i) sum[i][0]=sum[i-1][0]+b[i].val;

	for(int i=n;i>=1;--i) sum[i][1]=sum[i+1][1]+b[i].val;

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

		ans[b[i].id]+=1LL*b[i].val*(i-1)-sum[i-1][0];

		ans[b[i].id]+=sum[i+1][1]-1LL*(n-i)*b[i].val;

	}

	mi=0x3f3f3f3f3f3f3f3fLL;

	for(int i=1;i<=n;++i) mi=min(mi,ans[i]);

	cout<<mi/2<<"\n";

	return 0;

}

巴特西

luoguP3964 [TJOI2013]松鼠聚会

链接

思路

代码

最新文章

热门文章