695
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;
}
最後更新：2017-04-03 18:52:06