[语言月赛 202307] 塔台超频

Luogu

IDLGB3807

Time1000ms

Memory512MB

DifficultyP1

2023O2优化循环结构数组语言月赛

在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \cdots, a _ n$（$a _ 1 < a _ 2 < \cdots < a _ n$）的位置。每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i - b _ i, a _ i + b _ i]$ 范围内的塔台通讯。需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的**位置**处在 B 塔台的通讯范围内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通讯」。现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 $k$，之后**所有**塔台都会被加上 $k$ 的电压，通讯半径都会增大 $k$。这里的 $k$ 仅可为非负整数。现在要求你通过超频，使信号可以从 $1$ 号塔台**依次**通过 $2, 3, \cdots$ 号塔台传输到 $n$ 号塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。 ## Input 输入共 $n + 1$ 行。第一行为一个整数 $n$，代表塔台的数量。接下来 $n$ 行，每行两个整数 $a _ i, b _ i$，分别代表各个塔台的位置和初始通讯半径。 ## Output 输出共一行一个整数，代表为了达到目的，塔台超频需要的最小电压。 [samples] ## Note ### 数据规模与约定对于 $100\%$ 的数据，保证 $2 \leq n \leq 5 \times 10 ^ 5$，$0 \leq a _ i, b _ i \leq 10 ^ 9$。 | 测试点编号 | 特殊限制 | | :----------: | :----------: | | $1 \sim 2$ | $n \leq 10$，$a _ i, b _ i \leq 200$ | | $3$ | $a _ i = i$ | | $4 \sim 5$ | $b _ i = 0$ | | $6$ | 所有 $b _ i$ 相同 | | $7 \sim 10$ | 无特殊限制 |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202307] 塔台超频",
    "description": {
      "content": "在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \\cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \\cdots, a _ n$（$a _ 1 < a _ 2 < \\cdots < a _ n$）的位置。 每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \\cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i -",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3807"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \\cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \\cdots, a _ n$（$a _ 1 < a _ 2 < \\cdots < a _ n$）的位置。\n\n每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \\cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i -...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments