波动数列判定与单元素修改算法解析

1. 题目解析与波动数列定义

波动数列是信息学竞赛中一个有趣的数学概念。题目要求我们判断给定的数列是否能够通过修改最多一个元素，使其成为波动数列。我们先来明确波动数列的两种形式：

1.1 波动数列的两种模式

第一种波动模式（峰谷交替）：

• 奇数位元素 ≤ 偶数位元素
• 偶数位元素 ≥ 下一个奇数位元素
  即：a₁ ≤ a₂ ≥ a₃ ≤ a₄ ≥ a₅ ≤ ...

第二种波动模式（谷峰交替）：

• 奇数位元素 ≥ 偶数位元素
• 偶数位元素 ≤ 下一个奇数位元素
  即：a₁ ≥ a₂ ≤ a₃ ≥ a₄ ≤ a₅ ≥ ...

关键提示：波动数列的判定需要考虑数列的整体趋势，而不仅仅是局部关系。这也是本题的难点所在。

1.2 题目要求分析

题目要求我们判断是否可以通过修改最多一个元素，使得数列满足上述两种波动模式中的任意一种。这意味着我们需要：

1. 检查数列是否已经是波动数列
2. 如果不是，检查是否可以通过修改一个元素使其成为波动数列

2. 解题思路与算法设计

2.1 基本思路

我们可以采用双指针法同时检查两种波动模式：

1. 维护两个计数器cnt1和cnt2，分别记录两种波动模式需要修改的元素数量
2. 遍历数列，检查每个元素是否符合当前波动模式的要求
3. 如果不符合，增加相应计数器，并假设修改该元素使其符合要求
4. 最后判断两种模式中是否存在需要修改次数≤1的情况

2.2 关键算法实现

cpp复制#include<cstdio>
using namespace std;

int main(){
    int n;
    while(~scanf("%d",&n)){
        int cnt1=0, pre1, pre2, cnt2=0;
        scanf("%d",&pre2);
        pre1 = pre2;
        
        for(int i=2; i<=n; ++i){
            int now;
            scanf("%d",&now);
            
            // 检查第一种波动模式
            if((i&1) && now>pre1){  // 奇