题解 P3929 【SAC E#1 - 一道神题 Sequence1】

部分分： 如果给定一个序列，可以很容易的在 O(n) 时间内判断该序 列是否为波动序列。 首先判断该序列是否为波动序列，如果是，则直接输 出”Yes“。 否则，枚举修改哪一个数。 可以发现如一个数要被修改，则将其改为 ∞ 或 −∞ 一定不 会比修改为别的数不优。 所以将其修改为 ∞ 或 −∞ 后再次判断。 总复杂度 O(n^2)。 AC： 由于波动序列本质上只有 2 种，所以对于每一种波动序列， 求出将原序列变为这种波动序列最少需要修改几次。 如果两 个值的较小值不大于 1，则输出”Yes“，否则输出”No“。 问题变为求原序列变为某种波动序列需要的最小修改次数。 从前向后扫，如果遇到某个元素不满足要求，则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个，并将计数器加一。 最后计数器的值就是修改需要的最小次数。 总复杂度 O(n)。