首页 > ACM题库 > HDU-杭电 > HDU 4311-Meeting point-1-排序-[解题报告]HOJ
2015
05-23

HDU 4311-Meeting point-1-排序-[解题报告]HOJ

Meeting point-1

问题描述 :

It has been ten years since TJU-ACM established. And in this year all the retired TJU-ACMers want to get together to celebrate the tenth anniversary. Because the retired TJU-ACMers may live in different places around the world, it may be hard to find out where to celebrate this meeting in order to minimize the sum travel time of all the retired TJU-ACMers.
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone’s house. From any given cell, only 4 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.

输入:

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)

输出:

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)

样例输入:

4
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2

样例输出:

26
20
20
56
Hint
In the first case, the meeting point is (-1,-2); the second is (0,0), the third is (3,1) and the last is (-2,2)

/*
分析:
    树状数组+二分(可以不用二分)。
    果真是流年不利么。。。一开始就考虑会爆int的,就想到用64位了,
结果代码敲着敲着、一部分还是用了int,敲傻了么,1wa,囧~。。。
    简单说下思路吧:
        假设现在有n个点,把这些点都画到坐标纸上后第i个点在最左边、
    同时也是最下面,
    那么,假设大家都到i这里来:
                                第一个人到i这里,要走x1-xi+y1-yi;
                                第二个人到i这里,要走x2-xi+y2-yi;
                                。。。。。。
                                第n个人道i这里,要走 xn-xi+yn-yi;
    (看出来思路没?)简单整合一下,不就是:
                ans=(x1+x2+x3+…+xn)-n*xi+(y1+y2+…+yn)-n*yi;
    (括号里面的sum部分可以用树状数组、线段树呀来维护)
        但是,有些x<xi、有些x>xi,怎么办呢?那就将所有的x都排个序,
    再将所有的y排个序,同时让每个x记住自己对应的y值在排序后到了哪儿,
    在排序之后,再列出这个树状数组(线段树)。
        然后对x从小到大遍历,遍历的当前的点就作为当前的中心,让大
    家都来这个点,这个时候,刚刚的“(x1+x2+…+xn)”就可以分为两个部
    分了,一部分在当前点左边,一部分在当前点右边,这个借助树状数组
    在log(n)的时间内求出x方向上的ans_x;再找到当前点对应的y值,用同
    样的方法求出y方向上的ans_y,然后就可以得到ans=ans_x+ans_y了。

    PS:
        打字打上瘾了。。。
        头有点儿晕,就懒一下,没有维护排序后x对应的y在哪里,用的方法是
    每次都二分查找一下-、-I,不过只是大概让时间*2了而已,仍在可以接受范
    围以内。。。

                                                               2012-12-12
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define N 100011

int n;
struct A
{
    int x,y;
}E[N];
int x[N],y[N];

int lowbit[N];
__int64 C[2][N];								//0x、1y

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
void get_lowbit()
{
    int i;
    for(i=1;i<=100000;i++)    lowbit[i]=i&(-i);
}

__int64 sum(int K,int k)
{
    __int64 p=0;
    while(k>0 && k<=n)
    {
        p+=C[K][k];
        k-=lowbit[k];
    }
    return p;
}
void update(int K,int k,int dir)
{
    while(k>0 && k<=n)
    {
        C[K][k]+=dir;
        k+=lowbit[k];
    }
}
void init()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&E[i].x,&E[i].y);
        x[i]=E[i].x;
        y[i]=E[i].y;
    }
    x[0]=y[0]=-1111111111;
    qsort(x,n+1,sizeof(int),cmp);
    qsort(y,n+1,sizeof(int),cmp);
    memset(C,0,sizeof(C));
    for(i=1;i<=n;i++)
    {
        update(0,i,x[i]);
        update(1,i,y[i]);
    }
}
__int64 solve()
{
    int i;
    int low,mid,up;
    __int64 a,b;
    __int64 sum_x,sum_y;
    __int64 temp,ans;
    ans=100011;
    ans*=1000000000;
    sum_x=sum(0,n);
    sum_y=sum(1,n);
    for(i=1;i<=n;i++)
    {
        low=1;up=n;mid=(low+up)>>1;
        while(low<=up)
        {
            if(x[mid]<E[i].x)    low=mid+1;
            else                up=mid-1;
            mid=(low+up)>>1;
        }
        a=sum(0,low);
        temp=(__int64)low*E[i].x-a+sum_x-a-(n-(__int64)low)*E[i].x;
        low=1;up=n;mid=(low+up)>>1;
        while(low<=up)
        {
            if(y[mid]<E[i].y)    low=mid+1;
            else                up=mid-1;
            mid=(low+up)>>1;
        }
        b=sum(1,low);
        temp+=(__int64)low*E[i].y-b+sum_y-b-(n-(__int64)low)*E[i].y;
        if(temp<ans)    ans=temp;
    }
    return ans;
}

int main()
{
    int T;
    get_lowbit();
    scanf("%d",&T);
    while(T--)
    {
        init();
        printf("%I64d\n",solve());
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/8287715