HDU 4311 树状数组+二分

题意：给出10W个点，找出一个点使得每点按网格走到它的步数和最小，求最小步数和。每步这么走Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1).。

a点到达b点的步数为abs(b.x-a.x)+abs(b.y-a.y) 那么a点到所有点的步数和为abs(pi.x-a.x)+abs(pi.y-ay)所以按照从小到大的顺序吧x，y的值排序，二分查找a.x a.y在数组中的位置，就是给上面那个求和在打开就变成abs(numx*ax-sumpi.x(1~numx))+abs(pi.x(numx+1~n)-(n-numx)*a.x)就是x的和 同理求出y的和就可以了意思就是这样

 ans=(x1+x2+x3+...+xn)-n*xi+(y1+y2+...+yn)-n*yi; 不过需要考虑大小关系

(括号里面的sum部分可以用树状数组、线段树来维护)

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 100005
long long treex[maxn<<1],treey[maxn<<1],datax[maxn],datay[maxn],sumx,sumy;
struct cor
{
    long long x,y;
} data[maxn];
int n;
inline int Lowbit(int x)
{
    return x&(-x);
}
inline void Update(int pos,long long val,long long *tree)
{
    while(pos<=maxn)
        tree[pos]+=val,pos+=Lowbit(pos);
}
inline long long Query(int x,long long *tree)
{
    long long sum=0;
    while(x>0)
        sum+=tree[x],x-=Lowbit(x);
    return sum;
}
inline int find(long long val,long long *data)
{
    int l=0,r=n-1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(val==data[mid])
            return mid+1;
        else if(val<data[mid])
            r=mid-1;
        else
            l=mid+1;
    }
}
long long ab(long long a)
{
    return a<0?-a:a;
}
long long getans(cor a)
{
    long long sum,nowx,nowy;
    int numx,numy;
    numx=find(a.x,datax),numy=find(a.y,datay);
    nowx=Query(numx,treex),nowy=Query(numy,treey);
    sum=ab((long long)numx*a.x-nowx)+ab(sumx-nowx-(long long)(n-numx)*a.x)+ab((long long)numy*a.y-nowy)+ab(sumy-nowy-(long long)(n-numy)*a.y);
    return sum;
}
int main()
{
    int t;
    long long ans;
    scanf("%d",&t);
    while(t--)
    {
        sumx=sumy=0;
        memset(treex,0,sizeof(treex));
        memset(treey,0,sizeof(treey));
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%I64d%I64d",&data[i].x,&data[i].y),
                datax[i]=data[i].x,datay[i]=data[i].y,
                    sumx+=data[i].x,sumy+=data[i].y;
        sort(datax,datax+n);
        sort(datay,datay+n);
        for(int i=0; i<n; i++)
            Update(i+1,datax[i],treex),Update(i+1,datay[i],treey);
        ans=1e17;
        for(int i=0; i<n; i++)
            ans=min(ans,getans(data[i]));
        printf("%I64d\n",ans);
    }
    return 0;
}