前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【HDU 4311】Meeting point-1(前缀和求曼哈顿距离和)

【HDU 4311】Meeting point-1(前缀和求曼哈顿距离和)

作者头像
饶文津
发布2020-06-02 15:38:07
5080
发布2020-06-02 15:38:07
举报
文章被收录于专栏:饶文津的专栏

题目链接

正经解法:

给定n个点的坐标,找一个点,到其他点的曼哈顿距离之和最小。 n可以是100000。 大概要一个O(nlogn)的算法。 算曼哈顿距离可以把x和y分开计算排好序后计算前缀和就可以在O(1)时间内判断一个点到其他点的距离。

代码语言:javascript
复制
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100005
int t,n;
ll ans,sum[N],sx[N],sy[N];
struct p
{
    int i;
    ll x,y;
} a[N];
int cmpx(p a,p b)
{
    return a.x<b.x;
}
int cmpy(p a,p b)
{
    return a.y<b.y;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        sx[0]=sy[0]=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld%lld",&a[i].x,&a[i].y);
            a[i].i=i;
        }
        sort(a+1,a+n+1,cmpx);
        for(int i=1; i<=n; i++)
            sx[i]=sx[i-1]+a[i].x;
        for(int i=1;i<=n;i++)
            sum[a[i].i]=a[i].x*(i-1)-sx[i-1]+sx[n]-sx[i]-a[i].x*(n-i);
        sort(a+1,a+n+1,cmpy);
        for(int i=1; i<=n; i++)
            sy[i]=sy[i-1]+a[i].y;
        for(int i=1; i<=n; i++)
        {
            sum[a[i].i]+=a[i].y*(i-1)-sy[i-1]+sy[n]-sy[i]-a[i].y*(n-i);
            ans=(i==1)?sum[a[1].i]:min(ans,sum[a[i].i]);
        }
        printf("%lld\n",ans);
    }
}

缩小范围法:

另外一种做法,当时我就是这么想的,但是后来没敢交,觉得还是会wa。 因为本身就不是很可靠。 按x排序后,取中间x的附近点来计算(经过我多次提交,发现这个范围不能小于±220,这就是难点所在了,为什么是250左右,赛场上全凭直觉取值)。

代码语言:javascript
复制
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
struct p{ll x,y;}a[100005];
ll ABS(ll a){
    if(a<0)a=-a;
    return a;
}
ll dis(p a, p b){
    return ABS(a.x-b.x)+ABS(a.y-b.y);
}
int cmp(p a,p b){
    return a.x<b.x;
}
int main(){
    int t,n,s,e;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&a[i].x,&a[i].y);
        sort(a+1,a+1+n,cmp);
        s=n/2-223;
        e=n/2+223;
        if(s<1)s=1;
        if(e>n)e=n;
        ll ans=1LL<<60;
        for(int z=s;z<=e;z++){
            ll s=0;
            for(int i=1;i<=n;i++)
                s+=dis(a[z],a[i]);
            ans=min(s,ans);
        }
        printf("%lld\n",ans);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-07-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档