自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:20:25，当前版本为作者最后更新于2020-09-21 13:31:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upt on 2020.10.27：又修改了一些事实性错误，请管理员重新审核通过qwq。

upt on 2020.10.25：修改了一些事实性错误，请管理员重新审核通过qwq。

先从大到小排序，设 $dp_i$ 表示包括 $a_i$ 的情况下最小的答案

很容易推出方程 $dp_i=\min(dp_j+\max(k,a_i-a_j+1))\ \ \ (j \le i-1)$

但是直接搞的话是$n^2$的，跑不过去

我们可以把这个方程分成两部分：

1.$dp_i=\min(dp_j+a_i-a_{j+1}+1)$（当且仅当$j \le i-1$且$a_i-a_j+1\le k$）

这样的话，我们可以发现实际上是：$dp_i=\min(dp_j-a_{j+1})+a_i+1$，那么直接把每个 $dp_j-a_{j+1}$ 预处理出来就行了

2. $dp_i=\min(dp_j+k)$ （当且仅当 $j \le i-1$ 且 $k \le a_i-a_j+1$ ）

那么显然可以看成是$dp_i=\min(dp_j)+k$，那么显然当$j$最小的时候就可以了

怎么找到满足条件的$j$呢？二分就可以了

推完dp方程后怎么构造最后的答案呢？

如果 $a_i-a_{i-1} \le dp_i-dp_{i-1}$ 那么显然第 $i$ 个区间是和前一个数相邻的，所以可以说是右端点为 $a_i$，左端点为$a_i-k+1$

否则，显然是不相邻的，那么左端点是 $a_i$，右端点是$a_i+k-1$

还要考虑边界的情况。设 $Min$ 表示 $a_i$ 中最小的数。

• 如果左端点 $\le Min-1$，那么让这个点变为 $Min$，同时右端点也要相加。

• 如果右端点 $\ge n+1$，那么让这个点变为 $n$，同时左端点也要减。

最后还要记得记得排回来

code