自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:54:14，当前版本为作者最后更新于2017-10-07 15:26:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

部分分：

如果给定一个序列，可以很容易的在 O(n) 时间内判断该序 列是否为波动序列。 首先判断该序列是否为波动序列，如果是，则直接输 出”Yes“。 否则，枚举修改哪一个数。 可以发现如一个数要被修改，则将其改为 ∞ 或 −∞ 一定不 会比修改为别的数不优。 所以将其修改为 ∞ 或 −∞ 后再次判断。 总复杂度 O(n^2)。

AC： 由于波动序列本质上只有 2 种，所以对于每一种波动序列， 求出将原序列变为这种波动序列最少需要修改几次。

如果两 个值的较小值不大于 1，则输出”Yes“，否则输出”No“。

问题变为求原序列变为某种波动序列需要的最小修改次数。 从前向后扫，如果遇到某个元素不满足要求，则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个，并将计数器加一。

最后计数器的值就是修改需要的最小次数。 总复杂度 O(n)。