AT_arc175_c.[ARC175C] Jumping Through Intervals

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

给定 $N$ 个整数对 $(L_1, R_1), (L_2, R_2), \dots, (L_N, R_N)$ 。其中，对于所有 $1 \leq i \leq N$ ，都有 $L_i \leq R_i$ 。

我们称满足以下条件的 $N$ 元整数列 $A = (A_1, A_2, \ldots, A_N)$ 为良好整数列：

对于所有 $1 \leq i \leq N$ ，都有 $L_i \leq A_i \leq R_i$ 。

请在所有使得 $\displaystyle \sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的良好整数列 $A$ 中，输出字典序最小的一个。

数列的字典序定义如下：设数列 $S = (S_1, S_2, \ldots, S_{|S|})$ ， $T = (T_1, T_2, \ldots, T_{|T|})$ 。 $S$ 的字典序小于 $T$ ，当且仅当下列两条之一成立：

$|S| < |T|$ 且 $(S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|})$ 。
存在整数 $1 \leq i \leq \min\{|S|, |T|\}$ $1 \leq i \leq min {∣ S ∣, ∣ T ∣}$ ，使得
- $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$ ，
- 且 $S_i < T_i$ 。

输入格式

输入按以下格式从标准输入读入：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

请将答案以 $1$ 行输出：

$A_1$ $A_2$ $\ldots$ $A_N$

输入输出样例

输入#1
```
4
1 10
8 13
3 4
5 20
```
输出#1
```
8 8 4 5
```
输入#2
```
3
20 24
3 24
1 75
```
输出#2
```
20 20 20
```

输入#3

15
335279264 849598327
446755913 822889311
526239859 548830120
181424399 715477619
342858071 625711486
448565595 480845266
467825612 647639160
160714711 449656269
336869678 545923679
61020590 573085537
626006012 816372580
135599877 389312924
511429216 547865075
561330066 605997004
539239436 921749002

输出#3

526239859 526239859 526239859 467825612 467825612 467825612 467825612 449656269 449656269 449656269 626006012 389312924 511429216 561330066 561330066

说明/提示

数据范围

输入的所有数均为整数。
$2 \leq N \leq 5 \times 10^5$
$0 \leq L_i \leq R_i \leq 10^9$

样例解释 1

$(A_1, A_2, A_3, A_4) = (8, 8, 4, 5)$ 是一个良好整数列。此时 $\sum_{i=1}^{N-1} |A_{i+1} - A_i| = |8 - 8| + |4 - 8| + |5 - 4| = 5$ ，这是 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 的最小值。

样例解释 2

当使 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的良好整数列 $A$ 有多个时，请输出其中字典序最小的一个。

由 ChatGPT 4.1 翻译

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

首页