题目描述
小强很喜欢数列。有一天，他心血来潮，写下了一个数列。
阿米巴也很喜欢数列。但是他只喜欢其中一种：波动数列。
一个长度为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 = ;
for (int i = ; i <= n; i++, dir = !dir)
if (a[i] != a[i-] && (a[i] > a[i-]) != dir)
if (++cnt > )
return false;//从前向后扫，如果遇到某个元素不满足要求，则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个，并将计数器加一。
else
{
i++;
dir = !dir;
}
return true;
} int main()
{
while (scanf("%d", &n) >= )
{
for (int i = ; i <= n; i++)
scanf("%d", &a[i]); if (n <= )
printf("Yes\n");
else
printf(judge() || judge() ? "Yes\n" : "No\n");
}
//如果两个值的较小值不大于 1，则输出”Yes“，否则输出”No“。
return ;
}