题解
对于 \((a_1,b_1),(a_2,b_2)\) 的切比雪夫距离,可以看做成 \((\frac{a_1+b_1}{2},\frac{a_1-b_1}{2}),(\frac{a_2+b_2}{2},\frac{a_2-b_2}{2})\) 的曼哈顿距离
不信你分类讨论看看
某一点到其他点的曼哈顿距离,等于所有小于该点和大于该点的x,y的坐标差之和
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
struct node
{
ll val,id;
};
bool cmp(node a,node b)
{
return a.val<b.val;
}
void solve()
{
ll n;
cin>>n;
vector<node> heng,shu;
vector<ll> ans(n+1,0);
for(ll i=1;i<=n;i++)
{
ll x,y;
cin>>x>>y;
heng.push_back({x+y,i});
shu.push_back({x-y,i});
}
sort(heng.begin(),heng.end(),cmp);
sort(shu.begin(),shu.end(),cmp);
ll sum=0;
for(ll i=0;i<n;i++)
{
ll val=heng[i].val,id=heng[i].id;
ans[id]+=i*val-sum;
sum+=val;
}
sum=0;
for(ll i=n-1;i>=0;i--)
{
ll val=heng[i].val,id=heng[i].id;
ans[id]+=sum-(n-i-1)*val;
sum+=val;
}
sum=0;
for(ll i=0;i<n;i++)
{
ll val=shu[i].val,id=shu[i].id;
ans[id]+=i*val-sum;
sum+=val;
}
sum=0;
for(ll i=n-1;i>=0;i--)
{
ll val=shu[i].val,id=shu[i].id;
ans[id]+=sum-(n-i-1)*val;
sum+=val;
}
ll res=inf;
for(ll i=1;i<=n;i++)
{
res=min(res,ans[i]);
}
cout<<res/2<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
标签:P3964,shu,val,heng,ll,TJOI2013,sum,松鼠,id
From: https://www.cnblogs.com/pure4knowledge/p/18328183