题目解析

问题描述

给定一个长度为 $n$ 的数组 $a$，定义“美丽数组”为：对于所有 $1 \le i < n$，都有 $|a_i - a_{i+1}| \le 1$。

我们可以进行操作：选择相邻的两个数 $(a_{i-1}, a_i)$，将它们替换为一个数 $x$，其中 $x$ 可以是任意整数。

问最少需要多少次操作才能使数组变得美丽？如果不可能，输出 $-1$。

解题思路

第一步：检查是否已经美丽

如果原数组已经满足 $|a_i - a_{i+1}| \le 1$ 对所有 $i$ 成立，那么答案为 $0$。

第二步：检查是否存在局部极值

局部极大值：存在位置 $i$ 使得 $a_{i-1} < a_i > a_{i+1}$
局部极小值：存在位置 $i$ 使得 $a_{i-1} > a_i < a_{i+1}$

如果存在这样的极值点，我们可以在 一次操作 内使数组变得美丽。

证明（以局部极大值为例）： 假设 $a_{i-1} \le a_{i+1}$（另一种情况对称处理）。
当前序列为：$\dots, a_{i-2}, a_{i-1}, a_i, a_{i+1}, a_{i+2}, \dots$
我们选择操作相邻的 $(a_{i-1}, a_i)$，令 $x = a_{i+1}$，替换后序列变为：
$\dots, a_{i-2}, a_{i+1}, a_{i+1}, a_{i+2}, \dots$

此时：

• $|a_{i-2} - a_{i+1}|$ 与原来相比，不会变得更差（因为 $a_{i+1}$ 介于 $a_{i-1}$ 和 $a_i$ 之间或相等）
• $|a_{i+1} - a_{i+2}|$ 保持不变
• 新产生的相邻对 $(a_{i+1}, a_{i+1})$ 的差为 $0 \le 1$

所以一次操作即可得到美丽数组。

第三步：没有局部极值的情况

如果没有局部极值，意味着数组是 单调 的（严格递增或严格递减）。
此时，无论我们如何操作，都无法使任意相邻元素的差的绝对值 $\le 1$。

原因：
考虑操作替换 $(a_{i-1}, a_i)$ 为 $x$，新的相邻对为 $(a_{i-1}, x)$ 和 $(x, a_{i+1})$。
由于单调性，$|a_{i-1} - x| \ge |a_{i-1} - a_i|$ 且 $|x - a_{i+1}| \ge |a_i - a_{i+1}|$。
因此相邻元素的差不会减小，无法满足 $\le 1$ 的条件。

算法步骤

1. 检查是否已经美丽：遍历 $i$ 从 $1$ 到 $n-1$，如果存在 $|a_{i-1} - a_i| \le 1$，输出 $0$
2. 检查是否存在局部极值：遍历 $i$ 从 $1$ 到 $n-2$，如果 $a_{i-1} < a_i > a_{i+1}$ 或 $a_{i-1} > a_i < a_{i+1}$，输出 $1$
3. 否则输出 $-1$

时间复杂度：$O(n)$

代码注释

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 检查是否已经美丽
    for (int i = 1; i < n; i++) {
        if (abs(a[i - 1] - a[i]) <= 1) {
            cout << 0 << endl;
            return;
        }
    }
    
    // 检查是否存在局部极值
    for (int i = 1; i + 1 < n; i++) {
        if (a[i - 1] < a[i] && a[i] > a[i + 1]) {  // 局部极大值
            cout << 1 << endl;
            return;
        }
        if (a[i - 1] > a[i] && a[i] < a[i + 1]) {  // 局部极小值
            cout << 1 << endl;
            return;
        }
    }
    
    // 单调数组，无解
    cout << -1 << endl;
}

总结