BZOJ3170: [Tjoi 2013]松鼠聚会

切比雪夫距离，直接上公式转成哈密顿距离 然后就是找一个点到其他所有点的哈密顿距离和最短，将两维分开考虑，排个序O(n)就可以算出每个点到其他所有点x坐标的距离和，y坐标的距离和

注意longlong…

---

#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; const ll maxn = 110000; struct node { ll x,i; }p1[maxn],p2[maxn]; ll s1[maxn],s2[maxn]; bool cmp(node x,node y){return x.x<y.x;} ll n; int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) { ll x,y; scanf("%lld%lld",&x,&y); p1[i].x=x+y; p1[i].i=i; p2[i].x=x-y; p2[i].i=i; } sort(p1+1,p1+n+1,cmp); sort(p2+1,p2+n+1,cmp); for(ll i=2;i<=n;i++) { s1[p1[1].i]+=abs(p1[1].x-p1[i].x); s2[p2[1].i]+=abs(p2[1].x-p2[i].x); } for(ll i=2;i<=n;i++) { s1[p1[i].i]=s1[p1[i-1].i]-(p1[i].x-p1[i-1].x)*(n-i+1-i+1); s2[p2[i].i]=s2[p2[i-1].i]-(p2[i].x-p2[i-1].x)*(n-i+1-i+1); } ll ans=1; for(ll i=2;i<=n;i++) { if(s1[i]+s2[i]<s1[ans]+s2[ans]) ans=i; } printf("%lld\n",(s1[ans]+s2[ans])>>1); return 0; }