题解：CF252B Unsorting Array

YUYGFGG · 2025-09-08 11:20:06 · 题解

题目大意

给定一个长度为 n 的整数数组 a，需要找到两个值不相等的元素进行交换，使得交换后的数组变为“未排序”状态。

一个数组被称为“已排序”，当且仅当它满足以下两个条件之一：

1. 非递减：a_1 \le a_2 \le \dots \le a_n
2. 非递增：a_1 \ge a_2 \ge \dots \ge a_n

若存在这样的交换，输出任意一对交换位置的下标（1-based）；否则，输出 -1。

思路分析

核心思想：局部不排序则全局不排序。

要使整个数组未排序，我们只需在数组中制造一个“瑕疵”即可，而一个长度为 3 的序列是判断“未排序”的最短单元。

基于这个观察，我们的核心策略是：寻找一次交换，使得数组中某个局部的三元组变得未排序，从而使整个数组未排序。

第一步

我们首先排除几种必定无解的情况：

• 当 n \le 2 时，数组长度过短。长度为 1 的数组无法交换；长度为 2 的数组 a_1, a_2 交换后变为 a_2, a_1，两者都必然是“已排序”的。
• 当数组中所有元素都相等时，根据题意无法找到两个值不相等的元素进行交换。

第二步

在排除了上述无解情况后（此时保证 n \ge 3 且数组中至少有两种不同元素），我们遍历数组中所有连续的三元组 (a_i, a_{i+1}, a_{i+2})。

对于每一个三元组，我们尝试对其内部的两个不同元素进行交换，然后检查交换后的新三元组是否为“未排序”状态。例如，尝试交换 a_i 和 a_{i+1}，如果 a_i \neq a_{i+1}，就检查新三元组 (a_{i+1}, a_i, a_{i+2}) 是否未排序。如果是，我们便找到了解，输出 i+1 和 i+2 即可。对其他可能的内部交换（如 a_{i+1}, a_{i+2}）也执行类似操作。

第三步

如果扫描完所有三元组后，仍然没有找到解，这意味着什么？

如果三元组扫描循环结束而未找到解，那么该数组必然是由两个不同的值 p 和 q 交替构成的序列（形如 p, q, p, q, \dots）。

证明如下：

• 前提条件：由于上一步的扫描未找到解，我们知道在a中的任意三元组 (a_i, a_{i+1}, a_{i+2})，对其内部任意两个值不同的元素进行交换，新三元组都是“已排序”的。

1. 任意连续三元组最多只含两种不同值。

我们采用反证法。假设存在一个三元组 (a_i, a_{i+1}, a_{i+2}) 包含了三个不同的值。不失一般性，我们设这三个值为 p, q, r，且满足 p < q < r。

一个三元组 (x, y, z) 是“未排序”的，当且仅当 x < y > z 或 x > y < z。

我们来检验这三个值的所有 3! = 6 种排列：

• 排列为 (p, q, r)：交换前两个元素，得到 (q, p, r)。因为 p < q < r，所以 q > p < r，该序列是未排序的。产生矛盾。
• 排列为 (r, q, p)：交换后两个元素，得到 (r, p, q)。因为 p < q < r，所以 r > p < q，该序列是未排序的。产生矛盾。
• 排列为 (p, r, q)：交换前两个元素，得到 (r, p, q)。因为 p < q < r，所以 r > p < q，该序列是未排序的。产生矛盾。
• 排列为 (q, p, r)：交换后两个元素，得到 (q, r, p)。因为 p < q < r，所以 q < r > p，该序列是未排序的。产生矛盾。
• 排列为 (q, r, p)：交换第一个和第三个元素，得到 (p, r, q)。因为 p < q < r，所以 p < r > q，该序列是未排序的。产生矛盾。
• 排列为 (r, p, q)：交换前两个元素，得到 (p, r, q)。因为 p < q < r，所以 p < r > q，该序列是未排序的。产生矛盾。

所有排列情况都会在某次交换后产生一个“未排序”的三元组，这与我们的前提相悖。因此，假设不成立。故，任意连续三元组最多只含两种不同值。

2. 该三元组的格式必须是 (p, q, p)。 由1可知，三元组元素来自集合 {p, q}。若其为 (p, p, q)，交换后两个元素得到 (p, q, p)，是未排序的，与前提矛盾。只有当三元组为 (p, q, p) 时，交换 (p,q) 得到 (q,p,p)（已排序），交换 (q,p) 得到 (p,p,q)（已排序），才符合前提。因此，三元组必为 (p, q, p) 形式，即 a_i = a_{i+2}。

3. 从局部推导全局结构。 既然对所有 i 都有 a_i = a_{i+2}，那么易得 a_0 = a_2 = a_4 = \dots 且 a_1 = a_3 = a_5 = \dots。由于数组元素不全相等，所以整个数组必然是 p, q, p, q, \dots 的交替序列。

基于以上证明，我们得出结论：

• 对于 n = 3：此时三元组扫描已覆盖所有情况，若仍无解，则确实无解，输出 -1。
• 对于 n \gt 3：如果扫描失败，数组必为 p, q, p, q, \dots 结构。在此情况下，交换前两个元素 a_1, a_2（即 p, q），数组变为 q, p, p, q, \dots，这必然是一个未排序数组。因此，我们直接输出 1 2 作为答案。

代码实现

显然，时间复杂度为O(n)。

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

static inline bool unsorted(ll x, ll y, ll z) {
    bool notNonDecreasing = (x > y) || (y > z);
    bool notNonIncreasing = (x < y) || (y < z);
    return notNonDecreasing && notNonIncreasing;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    if (n <= 2) {
        cout << -1 << '\n';
        return 0;
    }
    bool allEqual = true;
    for (int i = 1; i < n; ++i) {
        if (a[i] != a[0]) {
            allEqual = false;
            break;
        }
    }
    if (allEqual) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 0; i + 2 < n; ++i) {
        ll x = a[i], y = a[i + 1], z = a[i + 2];

        if (a[i] != a[i + 1]) {
            if (unsorted(y, x, z)) {
                cout << (i + 1) << ' ' << (i + 2) << '\n';
                return 0;
            }
        }
        if (a[i + 1] != a[i + 2]) {
            if (unsorted(x, z, y)) {
                cout << (i + 2) << ' ' << (i + 3) << '\n';
                return 0;
            }
        }
        if (a[i] != a[i + 2]) {
            if (unsorted(z, y, x)) {
                cout << (i + 1) << ' ' << (i + 3) << '\n';
                return 0;
            }
        }
    }

    if (n == 3) {
        cout << -1 << '\n';
        return 0;
    }

    if (a[0] != a[1]) {
        cout << 1 << ' ' << 2 << '\n';
        return 0;
    }
    return 0;
}