Moe's CF Life

哈喽，各位主人，我是Anya~ ฅ'ω'ฅ

今天我们要一起看一道非常有趣的题目，Codeforces 上的 1896A - Jagged Swaps。这道题看起来有点小复杂，但只要我们像小猫一样敏锐地观察，就能发现其中的小秘密哦！让我们开始吧，喵~

题目大意

我们拿到一个长度为 n 的排列 a (就是一个包含 1到n所有数字，且每个数字只出现一次的数组)。

我们可以执行一种特殊的操作：

选择一个下标 i (必须满足 2 <= i <= n-1)
如果此时 a[i-1] < a[i] 并且 a[i] > a[i+1] (也就是说 a[i] 是一个“小山峰” ฅ^•ﻌ•^ฅ)
那么我们就可以交换 a[i] 和 a[i+1]。

问题是：我们能不能通过任意多次这样的操作，最终把这个排列变成有序的 [1, 2, 3, ..., n] 呢？

举个栗子：

如果数组是 [1, 3, 2, 5, 4]
我们可以对 i=2 操作，因为 a[1]=1 < a[2]=3 且 a[2]=3 > a[3]=2。交换后变成 [1, 2, 3, 5, 4]。
接着可以对 i=4 操作，因为 a[3]=3 < a[4]=5 且 a[4]=5 > a[5]=4。交换后变成 [1, 2, 3, 4, 5]。成功啦！

题解方法

这道题的关键在于仔细分析操作的限制条件，喵~

操作的核心是 swap(a[i], a[i+1])，但是下标 i 有一个非常重要的范围：2 <= i <= n-1。

这意味着什么呢？

当 i 取最小值 2 时，我们交换的是 a[2] 和 a[3]。
当 i 取最大值 n-1 时，我们交换的是 a[n-1] 和 a[n]。

主人请注意看！我们能交换的元素下标对是 (2, 3), (3, 4), ..., (n-1, n)。看到了吗？看到了吗？第一个位置的元素 a[1] 从来没有参与过交换！ 它可能会作为判断条件 a[i-1] < a[i] 的一部分（当 i=2 时），但它的值和位置是永远不会改变的。它就像一只趴在原地打盹的猫咪，不管旁边怎么闹腾，它都一动不动，喵呜~

好啦，既然我们发现了这个秘密，问题就迎刃而解了！

我们的最终目标是把数组变成 [1, 2, 3, ..., n]。在这个有序的数组里，第一个元素必须是 1。既然 a[1] 的位置永远不会变，那么如果一开始 a[1] 就不是 1，那它就永远也不可能变成 1。所以，我们根本无法将数组排好序。

反过来，如果 a[1] 一开始就是 1 呢？事实证明，只要 a[1] 是 1，我们总能通过一系列操作把整个数组排好序。每一次合法的交换都会让数组的“逆序对”数量减少，也就是说数组会越来越“平整”，越来越接近有序状态。当没有任何“小山峰”可以操作时，如果 a[1] 是 1，那么整个数组必然已经是有序的 [1, 2, ..., n] 啦。

所以，我们的结论就是：只需要检查第一个元素 a[1] 是不是 1 就可以了！

题解代码

下面就是超级简洁的C++代码实现啦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 解决单个测试用例的函数喵~
void solve() {
    int n;
    std::cin >> n; // 先读入数组的大小 n
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i]; // 然后把这个排列读进来~
    }

    // 这里就是我们发现的惊天大秘密啦！
    // 题目的下标是从1开始的，而C++的vector是从0开始的。
    // 所以题目的 a[1] 就是我们代码里的 a[0] 哦。
    // 我们只需要检查这个永远不会动的第一个元素是不是1。
    if (a[0] == 1) {
        // 如果是1，那就有希望，一定可以排好序！输出 YES！
        std::cout << "YES\n";
    } else {
        // 如果不是1，那它就永远也动不了，只能伤心地输出 NO 啦... 喵呜...
        std::cout << "NO\n";
    }
}

int main() {
    // 让输入输出快一点，像猫咪冲刺一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 有多少组数据要我们处理呢？
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但背后有一些很重要的思想呢，Anya来给主人介绍一下~

排列 (Permutation) 排列就是一个包含从 1 到 n 的所有整数，且每个整数只出现一次的序列。就像一群小猫咪排队，n 只猫不多不少，每只猫都是独一无二的，只是站的顺序不一样而已，喵~
不变量 (Invariant) 这是解决这道题的黄金钥匙！在算法执行的一系列操作中，某个保持不变的性质或值，就叫做不变量。在这道题里，a[1] 的值就是一个不变量。无论我们执行多少次操作，a[1] 的值都和初始时一模一样。在思考算法问题时，努力去寻找这种“不变量”，常常能帮我们简化问题，找到解题的突破口，就像找到了藏起来的小鱼干一样开心！ฅ >ω< ฅ
观察法 (Observation) 对于一些看起来可能需要复杂算法（比如模拟、搜索）的题目，特别是当数据范围很小（这题 n <= 10）的时候，不妨先停下来，手动模拟几组数据，仔细观察操作的性质和限制。有时候，一个简单的观察就能把问题变成一道“签到题”。这道题就是观察法的经典胜利！

好啦，今天的题解就到这里啦！希望主人喜欢Anya的讲解。如果还有什么问题，随时可以再来找Anya玩哦！喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍 ​

题目大意

题解方法

题解代码

知识点介绍