AT_codefestival_2015_qualA_d 壊れた電車
题目描述
由于高桥铁路的 $N$ 节编组列车部分车厢损坏，因此需要 $M$ 名维修工进行检查。
第 $i$ 位维修工最初位于第 $X_i$ 节车厢。每位维修工可以检查当前所在的车厢，并可以移动到相邻的车厢。检查车厢不需要时间，但移动到相邻车厢需要 $1$ 分钟。
当所有车厢都至少被 $1$ 位维修工检查过时，检查作业结束。请问最短需要多少分钟才能完成检查作业？
输入格式
输入通过标准输入按以下格式给出。
> $N$ $M$
> $X_1$
> $X_2$
> $\vdots$
> $X_M$
- 第 $1$ 行包含两个整数 $N\ (1\leq N\leq 10^9),\ M\ (1\leq M\leq 10^5,\ M\leq N)$，表示列车有 $N$ 节车厢，有 $M$ 名维修工。
- 接下来的 $M$ 行，每行一个整数 $X_i\ (1\leq X_i\leq N)$，表示第 $i$ 位维修工最初位于第 $X_i$ 节车厢。保证所有 $X_i$ 互不相同，且维修工信息按靠近第 $1$ 节车厢的顺序给出，即 $X_j < X_{j+1}\ (1\leq j\leq M-1)$。
输出格式
输出完成检查作业所需的最短时间（以分钟为单位），末尾输出换行符。
说明/提示
## 部分分
本题设有部分分。
- 若能正确解决 $N\leq 100$ 的数据集，可获得 $20$ 分。
- 若能正确解决 $N\leq 500,000$ 的数据集，可额外获得 $60$ 分。
- 若能正确解决无额外限制的数据集，可再获得 $20$ 分。
## 样例解释 1
如图所示，维修工可以按如下方式移动，在 $3$ 分钟内完成检查作业。
由 ChatGPT 4.1 翻译