题解：CF252B Unsorting Array

题目大意

给定一个长度为

n

的整数数组

a

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

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

非递减： $a_1 \le a_2 \le \dots \le a_n$
非递增： $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$ ，该序列是未排序的。产生矛盾。

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

该三元组的格式必须是 $(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}$ 。
从局部推导全局结构。 既然对所有 $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)

。

CPP

#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;
}

题解：CF252B Unsorting Array

文章操作

题目大意

思路分析

第一步

第二步

第三步

代码实现

相关推荐

评论

题解：CF252B Unsorting Array