AT_agc048_c.[AGC048C] Penguin Skating

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

有 $L$ 个格子横向排列成一行。格子从左到右依次编号为 $1,2,\ldots,L$ 。

有 $N$ 只企鹅站在这些格子上。企鹅从左到右依次编号为 $1,2,\ldots,N$ 。最初，第 $i$ 只企鹅站在第 $A_i$ 个格子上。这里， $1 \leq A_1 < A_2 < \ldots < A_N \leq L$ 。

你可以进行任意次数如下操作：

选择一只企鹅，让它向左或向右滑行。企鹅会一直滑，直到前方没有空格子为止。当企鹅滑到另一只企鹅所在格子的前一个格子，或者前方已经没有格子时，企鹅会停止。

例如，当 $N=3, L=10$ ，企鹅所在的格子为 $(2,3,7)$ 时，如果让企鹅 2 向右滑行，企鹅 2 会移动到第 6 个格子。如果让企鹅 3 向右滑行，企鹅 3 会移动到第 10 个格子。

你的目标是让每只企鹅 $i$ 最终站在第 $B_i$ 个格子上。这里， $1 \leq B_1 < B_2 < \ldots < B_N \leq L$ 。请判断目标是否可以达成，如果可以，请求出所需操作次数的最小值。

输入格式

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

$N$ $L$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

如果目标无法达成，输出 $-1$ ；如果可以达成，输出所需操作次数的最小值。

输入输出样例

输入#1
```
4 11
3 4 6 10
1 5 6 11
```
输出#1
```
3
```
输入#2
```
1 3
1
2
```
输出#2
```
-1
```

输入#3

10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

输出#3

说明/提示

限制条件

$1 \leq N \leq 10^5$
$N \leq L \leq 10^9$
$1 \leq A_1 < A_2 < \ldots < A_N \leq L$
$1 \leq B_1 < B_2 < \ldots < B_N \leq L$
输入的所有数均为整数。

样例解释 1

可以按如下方式操作：

让企鹅 1 向左滑行。企鹅的位置变为 $(1,4,6,10)$ 。
让企鹅 2 向右滑行。企鹅的位置变为 $(1,5,6,10)$ 。
让企鹅 4 向右滑行。企鹅的位置变为 $(1,5,6,11)$ 。

由 ChatGPT 4.1 翻译

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

首页