自动搬运

查看原文

来自洛谷，原作者为

	jiqimao **

搬运于2025-08-24 21:40:38，当前版本为作者最后更新于2020-06-29 22:48:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们注意到这个题本质是给定一个序列 $a_i$，然后需要给每个 $a_i$ 加上一个非负整数得到序列 $b_i$，使得最后的序列满足这样的条件：

可以将整个序列分成奇数段，使得一段内的数都相等，且相邻两段之间满足 $<,>,<,...>$ 的关系。即形成谷，峰，谷，峰...，谷这样的形式。

然后要最小化加上的数的和。

做法什么的可以看别的题解，这里主要证明一下结论。

结论是一定存在一组最优的 $b_i$ 满足对于任意 $i$，$\exists j,|i-j|\leq 2,b_i\in[a_j,a_j+1]$（网上写的结论是 $[a_j,a_j+2]$，我是证的过程中发现结论实际上更强。）

我们首先考虑一下如果每段长度都是 $1$（即相邻两数都不相等），那么有显然的结论：若 $i$ 在谷，那么 $b_i=a_i$，若 $i$ 在峰，那么 $b_i=\max(a_i,a_{i-1}+1,a_{i+1}+1)$。因为一个谷的位置我们一定不会给它加，而峰的位置只要加到比相邻两数大即可。

然而现在麻烦的地方在于段长度不为 $1$ 的时候。

我们的思路是先随便考虑一个合法的解，然后来改造它使得代价不增并使它满足一些特殊的性质。

对于一个 $b_i=a_i$ 的位置，我们称它为固定点，对于一个 $b_i\in [a_i,a_i+1]$ 的位置，我们称它为弱固定点。

下面讨论的段都是长度 $>2$ 的段。

首先考虑段的两端，对于谷，若它某一端不是固定点，那么可以让这个数减一，段中与它相邻的数加一。对于峰，若它某一端里面一个数不是固定点，那么可以让这一端加一，里面那个数减一。

然后考虑段的内部。

对于谷，我们考虑找到内部相邻的三个位置，满足中间的位置不是弱固定点。那么我们可以让中间这个位置减二，其他两个位置加一。

对于峰，我们考虑找到内部相邻的三个位置，满足两边的位置都不是固定点。那么我们可以让中间这个位置加二，其他两个位置减一。

画画图就可以知道我们的这些操作都不改变解的合法性。不停地做这些操作，直到无法操作时，可以发现对于长度 $>2$ 的段内部的数都满足上面提到的结论了。

然后我们把同一段看作一个数，它新的值 $a'_i$ 是段内 $a_i$ 的 $\max$。这时我们发现一段 $[l,r]$ 的 $a'_i$ 满足 $a'_i=\max(a_l,a_{l+1})=\max(a_{r-1},a_r)$

因为对于长度为 $2$ 的段显然，而长度大于 $3$ 的段经过上面的操作一定在与端点距离 $\leq1$ 的位置存在固定点。

我们现在只关心长度为 $2$ 的段..那么谷显然满足结论，因为 $a_i=\max(a_i,a_{i+1})$ 或 $\max(a_{i-1},a_i)$，而对于长度为 $2$ 的段构成的峰，如果这个峰取到了自己的 $a'$，那么满足条件，否则仍然有一点棘手。

我们现在约定这个峰被它右边的谷限制。即右边的 $a'$ 比较大。那么看起来当右边的谷长度为 $2$ 时，峰中的左元素与谷中的固定点会相距 $3$..当然证到这里仍然得到了取值个数为常数，只不过稍微弱了一点。但是我们并不满足。

考虑如果峰中的右元素不是固定点，那么我们可以让峰中的右元素减一，谷中的左元素加一，此时峰的长度就减一，变成长度为 $1$ 的峰。此时因为原来满足 $b=a'+1$，容易发现仍然满足条件。做不了这个操作的峰一定满足右元素是固定点，那么就满足性质了。 （这里注意一下每次我们操作完之后段的形态会变化，我们需要重新求 $a'$ 然后得到新答案）

我们来总结一下：

长度为 $1$ 谷：$b_i=a_i$

长度为 $2$ 谷：$\exists j,|i-j|\leq 1,b_i=a_j$

长度 $>2$ 谷：$\exists j,|i-j|\leq 1,b_i=a_j$ 或 $b_i\in[a_i,a_i+1]$

长度为 $1$ 峰：$\exists j,|i-j|\leq 2,b_i\in [a_j,a_j+1]$

长度为 $2$ 峰：$\exists j,|i-j|\leq 1,b_i=a_j$

长度 $>2$ 峰：$\exists j,|i-j|\leq 1,b_i=a_j$

综上，对于任意 $i$，$\exists j,|i-j|\leq 2,b_i\in[a_j,a_j+1]$。