BZOJ 3170 松鼠聚会(切比雪夫距离转曼哈顿距离)

时间：2024-01-18 20:25:14

题意

有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

思路

题目中的距离是切比雪夫距离，而切比雪夫距离与曼哈顿距离可以互相转化。

考虑二维笛卡尔坐标系的坐标原点\(O(0,0)\)，与它的切比雪夫距离为1的点的集合形成的图形是一个边长为2的正方形，与它的曼哈顿距离为1的点的集合形成的图形是一个边长为1的正方形，如果把这个边长为2的正方形旋转45度再缩小2倍，两个图形即可重合。

于是对应与点之间的关系，\((x,y)\)对应与\((\frac{x+y}{2},\frac{x-y}{2})\)。为了避免浮点数，我们把点的坐标再乘2。这样，切比雪夫距离就变成了曼哈顿距离了。

现在考虑枚举要汇合的那个点，因为曼哈顿距离为\(\left|x1-x2\right|+\left|y1-y2\right|\)。所以可以对x，y坐标单独考虑。

预处理出x坐标的前缀和和后缀和，这样\(\sum(x-x_i)=\sum x-\sum x_i\)

y坐标同理。

因为坐标范围比较大，需要对坐标进行离散化

时间复杂度\(O(nlogn)\)。

代码

# include<bits/stdc++.h>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-8

# define MOD 100000007

# define INF 1e16

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(register int i=a; i<=n; ++i)

# define FDR(i,a,n) for(register int i=a; i>=n; --i)

# define bug puts("H");

# define lch p<<1,l,mid

# define rch p<<1|1,mid+1,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline char nc(){

    static char buf[1000000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int Scan(){

    char ch=nc();int sum=0, f=1;

    if (ch=='-') f=-1, ch=nc();

    while(!(ch>='0'&&ch<='9'))ch=nc();

    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();

    return sum*f;

}

const int N=100005;

//Code begin....

struct Node{LL x, y;}node[N];

vector<LL>v1, v2;

LL Xsum1[N], Xsum2[N], Ysum1[N], Ysum2[N];

int Cx1[N], Cx2[N], Cy1[N], Cy2[N];

int main ()

{

    int n;

    LL x, y;

    scanf("%d",&n);

    FOR(i,1,n) {

        scanf("%lld%lld",&x,&y);

        node[i].x=x+y; node[i].y=x-y;

        v1.pb(node[i].x); v2.pb(node[i].y);

    }

    sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());

    int pos1=0, pos2=0;

    FOR(i,0,n-1) {

        if (i==0||v1[i]!=v1[i-1]) Xsum1[++pos1]=Xsum1[pos1-1]+v1[i], Cx1[pos1]=Cx1[pos1-1]+1;

        else Xsum1[pos1]+=v1[i], ++Cx1[pos1];

        if (i==0||v2[i]!=v2[i-1]) Ysum1[++pos2]=Ysum1[pos2-1]+v2[i], Cy1[pos2]=Cy1[pos2-1]+1;

        else Ysum1[pos2]+=v2[i], ++Cy1[pos2];

    }

    FDR(i,n-1,0) {

        if (i==n-1||v1[i]==v1[i+1]) Xsum2[pos1]+=v1[i], ++Cx2[pos1];

        else Xsum2[--pos1]=Xsum2[pos1+1]+v1[i], Cx2[pos1]=Cx2[pos1+1]+1;

        if (i==n-1||v2[i]==v2[i+1]) Ysum2[pos2]+=v2[i], ++Cy2[pos2];

        else Ysum2[--pos2]=Ysum2[pos2+1]+v2[i], Cy2[pos2]=Cy2[pos2+1]+1;

    }

    int siz1=unique(v1.begin(),v1.end())-v1.begin();

    int siz2=unique(v2.begin(),v2.end())-v2.begin();

    LL ans=1e16, tmp;

    FOR(i,1,n) {

        int idx=lower_bound(v1.begin(),v1.begin()+siz1,node[i].x)-v1.begin()+1;

        int idy=lower_bound(v2.begin(),v2.begin()+siz2,node[i].y)-v2.begin()+1;

        tmp=(node[i].x*Cx1[idx]-Xsum1[idx])+(Xsum2[idx+1]-node[i].x*Cx2[idx+1])+(node[i].y*Cy1[idy]-Ysum1[idy])+(Ysum2[idy+1]-node[i].y*Cy2[idy+1]);

        ans=min(ans,tmp);

    }

    printf("%lld\n",ans/2);

    return 0;

}

相关文章