题解 P5098 【[USACO2004OPEN]Cave Cows 3 洞穴里的牛之三】

· · 题解

\Large\texttt{My Blog}

题目链接：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，那么 \texttt{原式}=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，那么 \texttt{原式}=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

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