洛谷P3929 SAC E#1 - 一道神题 Sequence1【枚举】

题目描述

小强很喜欢数列。有一天，他心血来潮，写下了一个数列。

阿米巴也很喜欢数列。但是他只喜欢其中一种：波动数列。

一个长度为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，含义如题目所示。

输入输出样例

输入样例#1：

输出样例#1：

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\n");
        else
            printf(judge(0) || judge(1) ? "Yes\n" : "No\n");
    }
//如果两个值的较小值不大于 1，则输出”Yes“，否则输出”No“。
    return 0;
}