「Luogu 5098」Cave Cow 3

发表于 | | 阅读次数:
字数统计: 310 字

Description

题目链接：Luogu 5098

约翰的 $n$ 只奶牛在一个洞里探险，他们只能通过叫声交流。用坐标 $(x_i,y_i)$ 表示第 $i$ 只牛的位置，两只牛之间的曼哈顿距离决定了声音传播的时间，即第 $i$ 只牛和第 $j$ 只牛交流，需要的时间为 $|x_i-x_j|+|y_i-y_j|$。求出任意一对牛之间交流需要的时间的最大值。

Solution

由于 $i$ 和 $j$ 是无序的，我们强制 $x_i\ge x_j$，那么我们对 $y$ 进行分类讨论：

  1. 如果 $y_i\ge y_j$，那么 $\text{原式}=x_i-x_j+y_i-y_j=(x_i+y_i)-(x_j+y_j)$。答案最大为 $\max_{x+y}-\min_{x+y}$。
  2. 如果 $y_i<y_j$，那么 $\text{原式}=x_i-x_j-y_i+y_j=(x_i-y_i)-(x_j-y_j)$。答案最大为 $\max_{x-y}-\min_{x-y}$。

所以我们只需要维护 $x+y$ 和 $x-y$ 的最大值和最小值就行了。

时间复杂度：$O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <cstdio>
#include <algorithm>

const int inf=1<<30;

int main() {
    int n,a=-inf,b=inf,c=-inf,d=inf;
    for(scanf("%d",&n);n--;) {
        int x,y;
        scanf("%d%d",&x,&y);
        a=std::max(a,x+y);
        b=std::min(b,x+y);
        c=std::max(c,x-y);
        d=std::min(d,x-y);
    }
    printf("%d\n",std::max(a-b,c-d));
    return 0;
}
0%