HDU 4311 Meeting point-1

r囧r小猫 2022-07-29 09:03 156阅读 0赞

HDU 4311 : Meeting point-1 [http://acm.hdu.edu.cn/showproblem.php?pid=4311][http_acm.hdu.edu.cn_showproblem.php_pid_4311]

题目大意：给出若干个点，找到一个点，使得所有的点到这个点的曼哈顿距离之和最小，求这个最小的距离即可。

题目误区：找到的这个点，一定要是给定点中的一个，不是给定点中的，虽然能使曼哈顿距离之和最小，但也不满足题意，不可取。所以我们不能只看x，求得其他点距离任意一个点最小的距离。然后再去看y，这样有可能找到的不是最小的距离。

题目分析：由于点的个数比较多，而且坐标的范围也比较大，直接去找肯定会超时，所以，我们采用把x和y暂时分开来找的方法。也算是横向遍历每一个所给出的点，复杂度也就是O(n)。对于x，我们要先对x进行从小到大排序，然后把从x1到xn与x0之间的距离更新在结构体数组中，即结构体数组首位为0，由于我们要求的是最小的距离，所以把累加的距离也放在一个sumx的数组中，并把这样的顺序记录下来。然后同理对y进行同样的操作，之后把其他点到x0点的距离记录下来了。

而对于任意的xi，我们可以在其他点与x0的距离的基础上进行增减，画图解释一下：

![Center][]

代码实现如下：

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    
    using namespace std;
    
    const int MAXN=100005;
    struct node
    {
        long long x,y,id; //由于有两次排序，id用来记录第一次排完序之后的顺序
    }point[MAXN];
    long long sumx[MAXN],sumy[MAXN]; //分别用来存放从|x1x0|到|xnx0|的距离之和，和从|y1y0|到|yny0|的距离之和
    
    bool cmpx(node a,node b) //按x递增给结构体排序
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
    
    bool cmpy(node a,node b) //按y递增给结构体排序
    {
        if(a.y!=b.y)
            return a.y<b.y;
        return a.x<b.x;
    }
    
    int main()
    {
        int t,n;
        long long sum;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            for(int i=0; i<n; i++)
            {
                scanf("%lld%lld",&point[i].x,&point[i].y);
            }
    
            sort(point,point+n,cmpy);
            sumy[0]=0;
            point[0].id=0;
            for(int i=1; i<n; i++)
            {
                point[i].y=point[i].y-point[0].y;
                sumy[i]=sumy[i-1]+point[i].y;
                point[i].id=i;
            }
            point[0].y=0;
    
            sort(point,point+n,cmpx);
            sumx[0]=0;
            for(int i=1; i<n; i++)
            {
                point[i].x=point[i].x-point[0].x;
                sumx[i]=sumx[i-1]+point[i].x;
            }
            point[0].x=0;
    
            sum=sumx[n-1]+sumy[n-1];
            for(int i=1; i<n; i++)
            {
                long long ans= i * point[i].x - sumx[i-1] + sumx[n-1] - sumx[i] - (n - i - 1) * point[i].x;
                ans+=(point[i].id*point[i].y-sumy[point[i].id-1]+sumy[n-1]-sumy[point[i].id]-(n-point[i].id-1)*point[i].y);
                if(ans<sum)
                {
                    sum=ans;
                }
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4311]: http://http://acm.hdu.edu.cn/showproblem.php?pid=4311
[Center]: /images/20220728/65292dfc952c4751979257c1eac6c82b.png