题目描述
小强很喜欢数列。有一天，他心血来潮，写下了一个数列。
阿米巴也很喜欢数列。但是他只喜欢其中一种：波动数列。
一个长度为n的波动数列满足对于任何i（1 <= i < n），均有：
a[2i-1] <= a[2i] 且 a[2i] >= a[2i+1]（若存在） 或者
a[2i-1] >= a[2i] 且 a[2i] <= a[2i+1]（若存在）
阿米巴把他的喜好告诉了小强。小强便打算稍作修改，以让这个数列成为波动数列。他想知道，能否通过仅修改一个数（或不修改），使得原数列变成波动数列。
输入输出格式
输入格式：
输入包含多组数据。
每组数据包含两行。
第一行一个整数n表示数列的长度。
接下来一行，n个整数，表示一个数列。
输出格式：
对于每一组输入，输出一行Yes或No，含义如题目所示。
输入输出样例
5 1 2 3 2 1 5 1 2 3 4 5
Yes No
说明
对于30%的数据，n <= 10
对于另外30%的数据，m <= 1000
对于100%的数据，n <= 10^5，m <= 10^9
其中m = max|a[i]|（数列中绝对值的最大值）
【分析】：
如果给定一个序列，可以很容易的在 O(n) 时间内判断该序 列是否为波动序列。 首先判断该序列是否为波动序列，如果是，则直接输 出”Yes“。 否则，枚举修改哪一个数。 可以发现如一个数要被修改，则将其改为 ∞ 或 −∞ 一定不 会比修改为别的数不优。 所以将其修改为 ∞ 或 −∞ 后再次判断。 总复杂度 O(n^2)。
AC： 由于波动序列本质上只有 2 种，所以对于每一种波动序列， 求出将原序列变为这种波动序列最少需要修改几次。
如果两个值的较小值不大于 1，则输出”Yes“，否则输出”No“。
问题变为求原序列变为某种波动序列需要的最小修改次数。 从前向后扫，如果遇到某个元素不满足要求，则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个，并将计数器加一。
最后计数器的值就是修改需要的最小次数。 总复杂度 O(n)。
【代码】：
#include <iostream> #include <cstring> #include <cstdio> #define maxn 100010 using namespace std; int a[maxn]; int n; bool judge(bool dir)// 首先判断该序列是否为波动序列，如果是，则直接输 出”Yes“。 否则，枚举修改哪一个数。 { int cnt = 0; for (int i = 2; i <= n; i++, dir = !dir) if (a[i] != a[i-1] && (a[i] > a[i-1]) != dir) if (++cnt > 1) return false;//从前向后扫，如果遇到某个元素不满足要求，则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个，并将计数器加一。 else { i++; dir = !dir; } return true; } int main() { while (scanf("%d", &n) >= 1) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); if (n <= 3) printf("Yes "); else printf(judge(0) || judge(1) ? "Yes " : "No "); } //如果两个值的较小值不大于 1，则输出”Yes“，否则输出”No“。 return 0; }