hdu 4311 Meeting point-1 递推 多校联结赛（二） 第二题

hdu 4311 Meeting point-1 递推 多校联合赛（二） 第二题

这道提看完yy是最小生成数，一看点100000个，顿时吓尿了，最短路对校生成树都要n^2什么的啊，所以所以，没做出来

了解他的行走模式就知道，其实我们是可以x，y分开算的，这是什么概念，排序之后就是在x轴上可以分别算出每个点到其他距离和sumx，y轴上可以分别算出每个点到其他距离和sumy，对于询问的（x，y），可以二分查找到他在x轴上对应的sumx，y轴上对应sumy，在sumx+sumy就ok啦！！

至于我们怎么找算sumx，sumy，如果挨个算那就又是n^2啦，不好，想一个办法，就是递推先算出第一个点到说有点的距离sumx[1],然后就递推了，因为我们想右递推的过程中，里右面的点越来越进，左面的点越来越远，sumx[i]向sum[i+1]移动，远了左面点的个数*a[i+1]-a[i](从小到大排序的)，近了右面点的个数*a[i+1]-a[i],所以递推公式为sumx[i]=sumx[i-1]-(long long)(m-i)*(a[i]-a[i-1])+(long long)i*(a[i]-a[i-1]);注意中间会溢出的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100005
long long sumx[N],sumy[N];
int a[N],b[N],aa[N],bb[N],m;
long long find1(int x){
    int l=0,r=m-1;
    while(r>=l){
        int mid=(l+r)>>1;
        if(x>a[mid])
            l=mid+1;
        if(x<a[mid])
            r=mid-1;
        if(x==a[mid])
            return sumx[mid];
    }
    return sumx[l];
}
long long find2(int x){
    int l=0,r=m-1;

    while(r>=l){
        int mid=(l+r)>>1;
        if(x>b[mid])
            l=mid+1;
        if(x<b[mid])
            r=mid-1;
        if(x==b[mid])
            return sumy[mid];
    }
    return sumy[l];
}
int main(){
    freopen("in.txt","r",stdin);
    int n,x,y;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d%d",&a[i],&b[i]);
            aa[i]=a[i];
            bb[i]=b[i];
            sumx[i]=sumy[i]=0;
        }
        sort(a,a+m);
        sort(b,b+m);
        for(int i=1;i<m;i++){
            sumx[0]+=a[i]-a[0];
            sumy[0]+=b[i]-b[0];
        }
        for(int i=1;i<m;i++){
            sumx[i]=sumx[i-1]-(long long)(m-i)*(a[i]-a[i-1])+(long long)i*(a[i]-a[i-1]);
            sumy[i]=sumy[i-1]-(long long)(m-i)*(b[i]-b[i-1])+(long long)i*(b[i]-b[i-1]);
        }
//        for(int i=0;i<m;i++)
//            cout<<sumx[i]<<" ";
 //       cout<<endl;
//        for(int i=0;i<m;i++)
//            cout<<sumy[i]<<" ";
//        cout<<endl;

        long long sum,min1=300000000000000LL;
 //       cout<<min1<<endl;
        for(int i=0;i<m;i++){
            sum=find1(aa[i])+find2(bb[i]);
            if(sum<min1)
                min1=sum;
        }
        cout<<min1<<endl;
    }
    return 0;
}