专栏首页饶文津的专栏【HDU 4311】Meeting point-1(前缀和求曼哈顿距离和)

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

题目链接

正经解法:

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

#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左右,赛场上全凭直觉取值)。

#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);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU - 4342】History repeat itself(数学)

    饶文津
  • 【2016多校训练4】Multi-University Training Contest 4

    树状数组维护数字i前面有多少个比它小的数,即第几小。最左距离就是rank,最右距离就是max(原位置,终位置),求出距离极差即可。

    饶文津
  • 【cf849ABC】

    849A - Odds and Ends 问能否将序列划分为奇数个长度奇数的奇数开头奇数结尾的子区间。 一开始想dp。。不过没必要。

    饶文津
  • cf580E. Kefa and Watch(线段树维护字符串hash)

    首先有个神仙结论:若询问区间为$(l, r, d)$,则只需判断$(l + d, r)$和$(l, r - d )$是否相同

    attack
  • CF895 E. Eyes Closed(线段树 期望)

    attack
  • HDU6315 Naive Operations(线段树 复杂度分析)

    设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献

    attack
  • 牛客小白月赛23 部分题解

    B 题意:给定一个正整数 p 求一个最小的正整数 n,使得 n! 是 p 的倍数。

    用户7727433
  • 矩阵快速幂

    AngelNH
  • 【HDU 4614】Vases and Flowers(线段树区间更新懒惰标记)

    题目 0到n-1的花瓶,操作1在下标a开始插b朵花,输出始末下标。操作2清空[a,b]的花瓶,求清除的花的数量。 线段树懒惰标记来更新区间。 操作1,先查询0到...

    饶文津
  • 回旋星空

          题目链接: https://www.nowcoder.com/acm/contest/90/E

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券