AT_arc070_c [ARC070E] NarrowRectangles
题目描述
鹿のAtCoDeer君发现桌子上放着 $N$ 个纵向长度为 $1$ 的细长矩形。若将桌面视为一个二维平面，如下图所示，第 $i$（$1 \leq i \leq N$）个矩形的纵向范围为 $[i-1, i]$，横向范围为 $[l_i, r_i]$。
AtCoDeer君想要通过将这些矩形分别在水平方向上移动，使得所有矩形都连在一起。每个矩形在水平方向上移动距离 $x$ 需要支付 $x$ 的代价。请计算使所有矩形连成一块所需的最小总代价。在本题的约束条件下，可以证明该值为整数。
输入格式
输入经标准输入给出，格式如下：
> $N$
> $l_1$ $r_1$
> $l_2$ $r_2$
> $\cdots$
> $l_N$ $r_N$
输出格式
输出使所有矩形连成一块所需的最小总代价。
说明/提示
## 数据范围
- 所有输入均为整数。
- $1 \leq N \leq 10^5$
- $1 \leq l_i < r_i \leq 10^9$
## 部分分
- 若对满足 $1 \leq N \leq 400$ 以及 $1 \leq l_i < r_i \leq 400$ 的数据集输出正确，可获得 $300$ 部分分。
## 样例解释 1
将第 $2$ 个矩形向左移动 $2$ 达到最优。
## 样例解释 2
本来已经连成一块，无需移动。
由 ChatGPT 5 翻译