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

AT_arc070_c.[ARC070E] NarrowRectangles

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

鹿のAtCoDeer君发现桌子上放着 NN 个纵向长度为 11 的细长矩形。若将桌面视为一个二维平面，如下图所示，第 ii（1≤i≤N1 \leq i \leq N）个矩形的纵向范围为 [i−1,i][i-1, i]，横向范围为 [li,ri][l_i, r_i]。

AtCoDeer君想要通过将这些矩形分别在水平方向上移动，使得所有矩形都连在一起。每个矩形在水平方向上移动距离 xx 需要支付 xx 的代价。请计算使所有矩形连成一块所需的最小总代价。在本题的约束条件下，可以证明该值为整数。

输入格式

输入经标准输入给出，格式如下：

NN
l1l_1 r1r_1
l2l_2 r2r_2
⋯\cdots
lNl_N rNr_N

输出格式

输出使所有矩形连成一块所需的最小总代价。

输入输出样例

  • 输入#1

    3
1 3
5 7
1 3

    输出#1

    2

  • 输入#2

    3
2 5
4 6
1 4

    输出#2

    0

  • 输入#3

    5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

    输出#3

    1999999680

  • 输入#4

    5
123456 789012
123 456
12 345678901
123456 789012
1 23

    输出#4

    246433

  • 输入#5

    1
1 400

    输出#5

    0

说明/提示

数据范围

  • 所有输入均为整数。
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤li<ri≤1091 \leq l_i < r_i \leq 10^9

部分分

  • 若对满足 1≤N≤4001 \leq N \leq 400 以及 1≤li<ri≤4001 \leq l_i < r_i \leq 400 的数据集输出正确，可获得 300300 部分分。

样例解释 1

将第 22 个矩形向左移动 22 达到最优。

样例解释 2

本来已经连成一块，无需移动。

由 ChatGPT 5 翻译

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

首页