题解说明

问题背景：
给定一个长度为 $n$ 的数组 $a[1..n]$，我们希望通过最少的修改次数，使得数组满足“锯齿形”排列。
所谓锯齿形排列有两种模式：

• 模式1：$a[1] < a[2] > a[3] < a[4] > \dots$
• 模式2：$a[1] > a[2] < a[3] > a[4] < \dots$

即相邻元素交替大于或小于。题目要求输出最少需要修改多少个元素。

核心思路：

1. 两种模式分别计算：

   • 模式1：
     • 偶数位置 $i$ 要满足 $a[i] > a[i-1]$。
     • 奇数位置 $i$ 要满足 $a[i] < a[i-1]$。
     • 若不满足，则将 $a[i]$ 修改为极大值或极小值（保证后续比较不再冲突），并计数一次。
   • 模式2：
     • 偶数位置 $i$ 要满足 $a[i] < a[i-1]$。
     • 奇数位置 $i$ 要满足 $a[i] > a[i-1]$。
     • 同样，若不满足则修改并计数。

2. 贪心修改策略：

   • 当发现不满足条件时，直接修改当前元素为极大值（$+10^9$）或极小值（$-10^9$），确保后续比较不会再出错。
   • 这样保证了每次修改只影响当前位置，不会破坏之前的合法性。

3. 最终答案：

   • 分别得到模式1的修改次数 $res1$ 和模式2的修改次数 $res2$。
   • 输出 $\min(res1, res2)$ 即为最优解。

复杂度分析：

• 遍历数组两次，每次 $O(n)$。
• 总体复杂度 $O(n)$，空间复杂度 $O(n)$。
• 适合 $n \leq 5 \times 10^5$

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;  // 数组最大长度（5*10^5 +5，适配大规模数据）
int a[N], aa[N];        // a[]：用于临时修改的数组副本；aa[]：存储原始输入数组

int main() {
    // 读取输入（注释掉的文件操作表示可支持文件输入输出，此处使用标准输入）
    // freopen("watch.in","r",stdin);
    // freopen("watch.out","w",stdout);
    int n;
    scanf("%d", &n);  // 读取数组长度n

    // 读取原始数组数据到aa[]（从索引1开始存储）
    for (int i = 1; i <= n; i++)
        scanf("%d", &aa[i]);

    // -------------------------- 计算模式1的调整次数res1 --------------------------
    int res1 = 0;  // 模式1的调整次数

    // 将原始数组复制到临时数组a[]（避免修改原始数据）
    for (int i = 1; i <= n; i++)
        a[i] = aa[i];

    // 从第2个元素开始检查（需与前一个元素比较）
    for (int i = 2; i <= n; i++) {
        if (i & 1) {  // i为奇数位置（第3、5、...位）
            // 模式1规则：奇数位置元素需 < 前一个元素
            // 若不满足（a[i] >= a[i-1]），则调整当前元素
            if (a[i] >= a[i - 1]) {
                a[i] = -1e9;  // 设为极小值，确保后续比较中不会再违反规则
                res1++;       // 调整次数+1
            }
        } else {  // i为偶数位置（第2、4、...位）
            // 模式1规则：偶数位置元素需 > 前一个元素
            // 若不满足（a[i] <= a[i-1]），则调整当前元素
            if (a[i] <= a[i - 1]) {
                a[i] = +1e9;  // 设为极大值，确保后续比较中不会再违反规则
                res1++;       // 调整次数+1
            }
        }
    }

    // -------------------------- 计算模式2的调整次数res2 --------------------------
    int res2 = 0;  // 模式2的调整次数

    // 重新复制原始数组到a[]（重新开始另一种模式的判断）
    for (int i = 1; i <= n; i++)
        a[i] = aa[i];

    // 从第2个元素开始检查
    for (int i = 2; i <= n; i++) {
        if (i & 1) {  // i为奇数位置
            // 模式2规则：奇数位置元素需 > 前一个元素
            // 若不满足（a[i] <= a[i-1]），则调整当前元素
            if (a[i] <= a[i - 1]) {
                a[i] = +1e9;  // 设为极大值，避免后续违规
                res2++;       // 调整次数+1
            }
        } else {  // i为偶数位置
            // 模式2规则：偶数位置元素需 < 前一个元素
            // 若不满足（a[i] >= a[i-1]），则调整当前元素
            if (a[i] >= a[i - 1]) {
                a[i] = -1e9;  // 设为极小值，避免后续违规
                res2++;       // 调整次数+1
            }
        }
    }

    // 输出两种模式中调整次数较少的结果
    cout << min(res1, res2) << '\n';
    return 0;
}