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 100005long 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;}