P3964 [TJOI2013]松鼠聚会 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • interestingLSY
    log2的由来: 在有序的Y数组中二分查找当前点的坐标! 我比较懒就用了stl::lower_bound
  • attack
    写的真好,赞赞赞
  • 幸济蒸馒头
    %%%%%
  • 我_膜法师_蒟蒻
    orz
  • cellur925
    写的真好,赞赞赞
  • ROY1994
    请问dalao为什么该坐标时不 /2 但是最后除二呢 @interestingLSY
  • ROY1994
    @interestingLSY
  • 1517460958dyc
    楼上的,您想出小数吗?
  • Christopher_Yan
    赞赞赞
  • bjrjk
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
作者: interestingLSY 更新时间: 2018-02-27 22:42  在Ta的博客查看 举报    46  

[TJOI2013]松鼠聚会 题解 by LSY

先说一句,本题解中所有 $\color{Blue} \Delta X , \Delta Y$ 都指横纵坐标之差的绝对值


①好奇怪的距离啊

知道题中的距离为“切比雪夫距离”的dalao可以跳过这一部分

可以发现题中有一个Interes♂ting的地方:

两个点的距离定义为点 (x,y) 和它周围的8个点
(x-1,y)(x+1,y),(x,y-1),(x,y+1),
(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)
距离为1

这是什么意思?我们画图看看。

对于图1, $\color{Blue} Dis = \Delta Y $ . 对于图2, $\color{Blue} Dis = \Delta X $ (想想为啥?)

也就是说 $\color{Blue} Dis = max( \Delta X , \Delta Y)$

这个距离又叫做切比雪夫距离

再回去看一眼题:

题意说白了不就“是给你n个点,选一个点使得这个点到其他所有点的切比雪夫距离之和最小”嘛!

然而呢...

这样做的话,假设当前枚举的点为点 $i$ , 则当前答案为:

$$\color{Red} \sum_{k=1}^n \ qdis(k,i)$$ . . . ( $qdis(k,i)$表示 $k,i$两点的切比雪夫距离)

复杂度 $O(n^2)$ ,毫无疑问一定会 $GG$


②知道是切比雪夫距离又能怎样?

先介绍一下曼哈顿距离:

$$\color{Blue} Dis = \Delta X + \Delta Y$$

OI常用套路:将一个点 $\color{Blue}(x,y)$ 的坐标变为 $\color{Blue}(x+y,x-y)$ 后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离(想想为啥?)

反过来,将一个点 $\color{Blue}(x,y)$ 的坐标变为 $\color{Blue}(\frac{x+y}{2},\frac{x-y}{2})$ 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离!

这样我们就可以通过坐标变换,将切比雪夫距离转为曼哈顿距离。


③转成曼哈顿距离又如何?

转换成为曼哈顿距离后,假设当前枚举的点为点 $i$ , 则当前答案为:

$$\color{Red} \sum_{k=1}^n \ Mdis(k,i)$$ . . . ( $Mdis(k,i)$表示 $k,i$两点的曼哈顿距离)

骗人啊,不都差不多吗,不也是 $O(n^2)$?

别着急,我们一步步推。

$$\color{Red} \sum_{k=1}^n \ Mdis(k,i)$$

$$\color{Red}=Mdis(1,i)+Mdis(2,i)+Mdis(3,i)+...+Mdis(n,i)$$

$$\color{Red}=\Delta X(1,i)+\Delta Y(1,i) + \Delta X(2,i)+\Delta Y(2,i) + ... + \Delta X(n,i)+\Delta Y(n,i)$$

$$\color{Green}=\lgroup \Delta X(1,i)+\Delta X(2,i)+...+\Delta X(n,i) \rgroup + \color{Blue}\lgroup \Delta Y(1,i) + \Delta Y(2,i) + ... +\Delta Y(n,i) \rgroup $$

emmmmmm....事情开始变得有趣.....有点前缀和的意思.....

别忘了本题解中所有 $\color{Blue} \Delta X , \Delta Y$ 都指横纵坐标之差的绝对值,那么就会有两种情况。(就拿 $\color{Blue}Y$ 这边来说吧, $\color{Green}X$这边类似。我比较懒就不打了

假定现在各个点的 $\color{Blue}Y$是有序的,那么

$$\color{Blue}\Delta Y(1,i) + \Delta Y(2,i) + ... +\Delta Y(n,i)$$

$$\color{Blue}=|Y_i-Y_1|+|Y_i-Y_2|+...+|Y_i-Y_n|$$

$$\color{Blue}=(Y_i-Y_1)+(Y_i-Y_2)+...+(Y_i-Y_i) \quad + \quad$$

$$\color{Red}(Y_{i+1}-Y_i)+(Y_{i+2}-Y_i)+...+(Y_n-Y_i)$$

$$\color{Blue}=(i \cdot Y_i\ -\ \sum_{k=1}^i Y_k) \quad + \quad \color{Red}(\sum_{k=i+1}^n Y_k\ -\ (n-i) \cdot Y_i)$$

再定睛一看,是不是可以用前缀和来维护!

这样计算一次的复杂度...就会大大降低,至少不用 $O(n)$


④真正的复杂度?

坐标变换: $\color{Blue}O(n)$

前缀和处理: $\color{Blue}O(n)$

枚举每个点: $\color{Blue}O(n)$

计算一个点的答案: $\color{Blue}O(log_2n)$

总复杂度: $\color{Red}O(n \cdot log_2n)$

仔细想想这个log哪来的,答案会在评论区里ovo


⑤Code:

这里只列出关键部分: 为了防止爆 $long\ long$, 某些地方使用 $unsigned\ long\ long$, 即 $ull$

#define For(i,j) for( rg int (i) = 1 ; (i) <= (j) ; (i)++ )
#define For0(i,j) for( rg int (i) = 0 ; (i) < (j) ; (i)++ )
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
#define MAXN 100010

int n;
ll x[MAXN], y[MAXN];
ll inpx[MAXN], inpy[MAXN];
ll sumx[MAXN], sumy[MAXN];
ull ans = ULONG_LONG_MAX;

il void Getsum(){
    sumx[0] = sumy[0] = 0;
    For(i,n){
        sumx[i] = sumx[i-1] + x[i];
        sumy[i] = sumy[i-1] + y[i];
    }
}
il ull Try( int u ){
    ull ansx = 0 , ansy = 0;

    int xpos = lower_bound(x+1,x+1+n,inpx[u]) - x;
    ansx += xpos*inpx[u] - sumx[xpos];
    ansx += sumx[n] - sumx[xpos] - (n-xpos)*inpx[u];

    int ypos = lower_bound(y+1,y+1+n,inpy[u]) - y;
    ansy += ypos*inpy[u] - sumy[ypos];
    ansy += sumy[n] - sumy[ypos] - (n-ypos)*inpy[u];

    return ansx + ansy;
}

int main(){
    Read(n);
    For(i,n){
        ll a,b;
        Read(a,b);
        x[i] = inpx[i] = a+b;
        y[i] = inpy[i] = a-b;
    }

    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    Getsum();

    For(i,n){
        ull tans = Try(i);
        Mymin(ans,tans);
    }
    printf("%llu\n",ans >> 1LL);

    return 0;
}

⑥没听懂?

没事,随便问吧

私信我或者在评论区中留言均可(但留言要@我0v0)

如果发现错误,请务必指出0v0

没错就点个赞(逃

评论

  • cellur925
    偶遇学长%%%
  • 星之ζ泪殇
    orz
作者: HiJ1m 更新时间: 2017-11-30 20:59  在Ta的博客查看 举报    6  

我的博客原文链接:http://www.cnblogs.com/Elfish/p/7931766.html

本题两点间的距离是max(|x1-x2|,|y1-y2|),曾经在黄学长的博客里看到过一个转化  求这个距离可以把点的坐标都转化成 (x+y)/2,(x-y)/2  然后的曼哈顿距离就是这个了

这个好像叫 切比雪夫距离

之后我们预处理前缀和,枚举源点就可以了。

记得都开longlong 我WA的很悲惨

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int read(){
    int x=0,t=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*t; 
} 
struct Node{
    long long X,Y; 
}a[MAXN]; 
int N,x[MAXN],y[MAXN],pos;
long long ans=1ll<<62,s1[MAXN],s2[MAXN];
int main()
{
    N=read();
    for(int i=1;i<=N;i++){
        int p=read(),q=read();
        x[i]=a[i].X=p+q;
        y[i]=a[i].Y=p-q;
    }
    sort(x+1,x+N+1);
    sort(y+1,y+N+1);
    for(int i=1;i<=N;i++)
        s1[i]=s1[i-1]+x[i],
        s2[i]=s2[i-1]+y[i];
    for(int i=1;i<=N;i++){
        long long tmp=0;
        pos=lower_bound(x+1,x+N+1,a[i].X)-x;
        tmp+=s1[N]-s1[pos]-a[i].X*(N-pos)+a[i].X*pos-s1[pos];
        pos=lower_bound(y+1,y+N+1,a[i].Y)-y;
        tmp+=s2[N]-s2[pos]-a[i].Y*(N-pos)+a[i].Y*pos-s2[pos];
        ans=min(ans,tmp);
    }
    printf("%lld\n",ans/2);
    return 0;
}

评论

  • interestingLSY
    %%%
  • bztMinamoto
    卧槽你居然还活着
作者: quantum11 更新时间: 2018-12-04 15:30  在Ta的博客查看 举报    3  

题意为给定一些点,选其中一个点使其他点到这个点的切比雪夫距离之和最小,求出最小距离。

切比雪夫距离=$\max(\Delta x,\Delta y)$,因为取$max$不太好优化,我们可以把它转化为曼哈顿距离$(\Delta x+\Delta y)$来做。

将$(x,y)$变为$(\frac{x+y}2,\frac{x−y}2)$ 后,原坐标系中的切比雪夫距离$=$新坐标系中的曼哈顿距离

将$(x,y)$变为$(x+y,x−y)$后,原坐标系中的曼哈顿距离$=$新坐标系中的切比雪夫距离

如果$x,y$数组都是有序的,那么

$$ans_x=\sum ^{n}_{j=1}\Delta(j,i)$$

$$=\Delta x(1,i)+\Delta x(2,i)+\Delta x(3,i)+...+\Delta x(n,i)$$

$$=(x_i-x_1)+(x_i-x_2)+...+(x_i-x_{i-1})+(x_{i+1}-x_i)+(x_{i+2}-x_i)+(x_n-x_i)$$

$$=\sum_{j=1}^{i-1}(x_i-x_j)+\sum_{j=i+1}^n(x_j-x_i)$$

$$=\sum_{j=1}^n x_j-2\times\sum_{j=1}^i x_j-x_i\times(n-2\times i)$$

然后就用前缀和优化一下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;
    return x*f;
}
struct A{ll x,y;}a[N];ll x[N],y[N],s1[N],s2[N],ans=1ll<<62;int n,p,u,v;
int main(){
    n=read();
    for(int i=1;i<=n;++i) u=read(),v=read(),a[i].x=x[i]=u+v,a[i].y=y[i]=u-v;
    sort(x+1,x+n+1);sort(y+1,y+n+1);
    for(int i=1;i<=n;++i) s1[i]=s1[i-1]+x[i],s2[i]=s2[i-1]+y[i];
    for(int i=1;i<=n;++i){
        ll tmp=0;
        p=lower_bound(x+1,x+n+1,a[i].x)-x;tmp+=s1[n]-2*s1[p]-a[i].x*(n-2*p);
        p=lower_bound(y+1,y+n+1,a[i].y)-y;tmp+=s2[n]-2*s2[p]-a[i].y*(n-2*p);
        ans=min(ans,tmp);
    }return !printf("%lld",ans>>1);
}

评论

  • 还没有评论
作者: yukuai26 更新时间: 2018-03-04 09:21  在Ta的博客查看 举报    2  

涨姿势了 题意,求出以给定点中一点为起点的所有点的最小切比雪夫距离和的最小值

切比雪夫距离=max(|x1-x2|+|y1-y2|);

此题的切比雪夫距离和十分难缠,但是我们可以把他转换为曼哈顿距离,这样就可以快速求出来

让我们愉快地推公式

曼哈顿距离=|x1-x2|+|y1-y2|=max(x1-x2+y1-y2,x1-x2+y2-y1.......)

=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)

我们发现右式是一个切比雪夫距离,这样我们把给定的x,y带进左式,就可以得到新的x',y'

其中x'=x+y>>1; y'=x-y>>1;

这样就算一下曼哈顿距离就行了

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define inf 1000000000000006
#define mod 1000000007
#define put putchar('\n')
#define int ll
using namespace std;
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
int t,ans,n,m,sumx[N],sumy[N],x,y;
struct xx{
    int x,y,fy,fx,i;
}z[N];
bool cmpx(xx a,xx b){return a.x<b.x;}
bool cmpy(xx a,xx b){return a.y<b.y;}
signed main(){
//  freopen(".in","r",stdin);freopen(".out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++){
        x=read();y=read();z[i].i=i;
        z[i].x=x+y;z[i].y=x-y;
    }
    sort(z+1,z+n+1,cmpx);
    for (int i=1;i<=n;i++){
        z[i].fx=i;
        sumx[i]=sumx[i-1]+z[i].x;
    }
    sort(z+1,z+n+1,cmpy);
    for (int i=1;i<=n;i++){
        z[i].fy=i;
        sumy[i]=sumy[i-1]+z[i].y;
    }
    ans=inf;
    for (int i=1;i<=n;i++){
        t=0;
        t=-sumx[z[i].fx]+z[i].x*z[i].fx-sumy[z[i].fy]+z[i].y*z[i].fy-sumx[z[i].fx]-z[i].x*(n-z[i].fx)+sumx[n]-sumy[z[i].fy]-z[i].y*(n-z[i].fy)+sumy[n];
        ans=min(ans,t);
    }
    wrn(ans/2);
    return 0;
}

评论

  • 还没有评论
作者: Heartlessly 更新时间: 2019-06-10 21:51  在Ta的博客查看 举报    0  

Description

给定 $n$ 个点,每个点的坐标为 $(x_i,y_i)$,且点 $(x,y)$ 到它周围 $8$ 个点 $(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)$ 的距离均为 $1$ 。现要找到一个点,使其它点到这个点的距离和最小,输出这个最小值。

$(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$

Solution

很容易看出这道题属于 切比雪夫距离 的一般模型。即对于两个点 $(x_1, y_1),(x_2,y_2)$,它们之间的距离为 $$ \max(\left | x_1 - x_2\right | , \left | y_1 - y_2\right | ) $$ 直接求 切比雪夫距离 似乎很困难?考虑把 切比雪夫距离 转化为 曼哈顿距离,即把每个点的坐标 $(x,y)$ 变为 $(\frac{x + y}{2}, \frac{x - y}{2})$ 。(不会的请学习 常用距离算法详解

枚举所选的点 $i$,我们只需要计算其它点到它的曼哈顿距离和即可。

如果某个点 $j$ 的横坐标 $x_j \leq x_i$,则它的对总距离的贡献为 $x_i - x_j$,反之则为 $x_j - x_i$ 。

这样就可以分两种情况讨论了。

设前 $k$ 个点的横坐标都 $\leq x_i$,那么所有点横坐标的贡献和为

ZnGuuV.png

对于 $\sum\limits_{i = 1}^k x_i$ 和 $\sum\limits_{i = k + 1}^n x_i$,我们可以预处理出 $x$ 的前缀和后 $O(1)$ 求得。

怎么求 $k$ 呢?显然可以将横坐标排序后二分得到。

纵坐标 $y$ 的计算方法与上面一样。时间复杂度为 $O(n \log n)$ 。

切比雪夫距离 转成 曼哈顿距离 时要除以 $2$,为了避免出现小数,我们可以横坐标和纵坐标同时乘上 $2$,最后答案除以 $2$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
int n, x[MAXN + 5], y[MAXN + 5], p[MAXN + 5], q[MAXN + 5];
LL ans = 0x7fffffffffffffff, prex[MAXN + 5], prey[MAXN + 5];

int main() {
    read(n);
    for (int a, b, i = 1; i <= n; ++i) {
        read(a), read(b);
        x[i] = p[i] = a + b, y[i] = q[i] = a - b;//转曼哈顿距离,且乘上 2 
    }
    sort(p + 1, p + n + 1), sort(q + 1, q + n + 1);//排序 
    for (int a, b, i = 1; i <= n; ++i)//维护前缀和 
        prex[i] = prex[i - 1] + p[i], prey[i] = prey[i - 1] + q[i];
    for (int posx, posy, i = 1; i <= n; ++i) {
        posx = lower_bound(p + 1, p + n + 1, x[i]) - p;
        posy = lower_bound(q + 1, q + n + 1, y[i]) - q;
        //二分找到 x[i] 和 y[i] 是所有点中第几个大的 
        LL sumx, sumy;
        sumx = (LL) posx * x[i] - prex[posx] + 
        prex[n] - prex[posx] - (LL) (n - posx) * x[i];//计算横坐标贡献 
        sumy = (LL) posy * y[i] - prey[posy] + 
        prey[n] - prey[posy] - (LL) (n - posy) * y[i];//计算纵坐标贡献 
        ans = min(ans, sumx + sumy);
    }
    write(ans / 2);//答案不要忘记除回去 
    putchar('\n');
    return 0;
}
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。