题目详情题解（0）讨论（0）提交记录（0）

AT_abc419_c.[ABC419C] King's Summit

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 10910^9 行 10910^9 列的网格。记 (i,j)(i, j) 表示从上往下第 ii 行、从左往右第 jj 列的格子。

网格上有 NN 个人。初始时，第 ii 个人在格子 (Ri,Ci)(R_i, C_i)。

时间从 00 开始。每个人可以在时间 1,2,3,4,…1, 2, 3, 4, \ldots 时进行如下操作：

  • 保持当前位置不动，或者移动到 88 邻接的格子。禁止离开网格。具体来说，若当前位置为 (i,j)(i, j)，则可以移动到存在的 (i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) 之一。假设移动不耗时。

请你求出 NN 个人能够汇聚到同一个格子的最小时间。

输入格式

输入从标准输入读入，格式如下：

NN
R1 C1R_1\ C_1
R2 C2R_2\ C_2
⋮\vdots
RN CNR_N\ C_N

输出格式

输出答案。

输入输出样例

  • 输入#1

    3
2 3
5 1
8 1

    输出#1

    3

  • 输入#2

    5
6 7
6 7
6 7
6 7
6 7

    输出#2

    0

  • 输入#3

    6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

    输出#3

    44

说明/提示

样例解释 1

如果每个人按如下方式移动，则所有人可以在时间 33 时汇聚到格子 (5,4)(5, 4)。

  • 时间 11：第 1 个人移动到 (3,4)(3, 4)，第 2 个人移动到 (6,2)(6, 2)，第 3 个人移动到 (7,2)(7, 2)。
  • 时间 22：第 1 个人移动到 (4,4)(4, 4)，第 2 个人移动到 (5,3)(5, 3)，第 3 个人移动到 (6,3)(6, 3)。
  • 时间 33：第 1、2、3 个人都移动到 (5,4)(5, 4)。

样例解释 2

所有人一开始就在同一个格子。

数据范围

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ri,Ci≤1091 \leq R_i, C_i \leq 10^9
  • 所有输入值均为整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页