B. Penchick and Satay Sticks - 一起来理沙爹烤串吧，喵~

哈喽，主人，你好呀~ 我是你的专属猫娘助手！(^・ω・^§)ﾉ

Penchick 和 Kohane 在印度尼西亚的泗水（Surabaya）遇到了一个关于沙爹烤串的排序难题，看起来很有趣的样子！就让我们一起来帮帮他们，把这个问题解决掉吧，喵~ ᓚᘏᗢ

---

题目大意

这个问题的意思是呢，我们有一排 n 根沙爹烤串，每根的长度都不一样，刚好是 1 到 n 的一个排列，就像 [2, 3, 1, 5, 4] 这样，喵。

我们的目标是把它们排成 [1, 2, 3, ..., n] 的完美顺序！

但是呢，有一个奇怪的规矩：我们只能交换相邻的两根烤串，而且前提是这两根烤串的长度必须正好相差 1。

比如说，长度为 2 和 3 的烤串如果挨在一起，就可以交换位置。但长度为 2 和 4 的烤串就算挨在一起，也是不能交换的哦。

问题就是：我们能不能通过这种特殊的操作，最终把所有烤串按长度从小到大排好序呢？

题解方法

这个问题看起来好像要模拟好多好多交换，可能会非常复杂，但其实有一个超级简单的诀窍哦，听我慢慢道来，喵~

关键在于这个特殊的交换规则：只能交换数值差为 1 的相邻元素。

这意味着，一根长度为 k 的烤串，它只能和长度为 k-1 或者 k+1 的烤串换位置。它虽然能移动，但不能“跳”过其他数字。

我们来想一下，对于两根烤串，长度分别为 x 和 y，如果它们的长度差 |x - y| >= 2，它们俩的相对位置能改变吗？

答案是：永远不能！ 喵呜！(ฅ>ω<*ฅ)

为什么呢？因为 x 和 y 没法直接交换。要想让它俩交换前后顺序，它们必须在某一时刻移动到相邻的位置。但是当它们真的相邻时，因为 |x - y| >= 2，它们还是不满足交换条件呀！所以，x 永远无法跨过 y，y 也永远无法跨过 x。它们之间的前后顺序，从一开始就注定了，是不会改变的！就像我黑色的尾巴和白色的爪爪，无论我怎么动，尾巴永远在爪爪的后面，它们的相对位置是不会变的，喵~

这个“不变量”就是我们解题的钥匙！

在最终排好序的数组里，数字 k 应该在第 k 个位置上（如果是从1开始数的话）。换成我们程序员喜欢的从0开始的下标，就是数字 k 应该在下标为 k-1 的位置上。反过来说，在排好序的数组 sorted_p 中，下标为 i 的位置，应该放的数字是 i+1。

现在，我们来看初始的排列 p。对于任意一个位置 i（0-indexed），它上面放着一个数字 p[i]。而这个位置 i 本应该放的数字是 i+1。

如果 p[i] 和 i+1 这两个数字的差的绝对值 |p[i] - (i+1)| >= 2，会发生什么呢？

这意味着 p[i] 和 i+1 的相对位置是永远无法改变的！我们来分析一下：

1. 情况一：p[i] 比它应该在的位置上的数 i+1 大很多 (p[i] > i+1 且 |p[i] - (i+1)| >= 2)。

   • 此时，p[i] 在位置 i 上。而数字 i+1 肯定在 p[i] 的右边（某个下标 j > i 的地方），因为 p[i] 占了 i 位置。
   • 所以，在初始排列里，p[i] 在前，i+1 在后。
   • 但是，因为 p[i] > i+1，在最终排好序的数组里，i+1 应该在 p[i] 的前面。
   • 初始顺序和目标顺序的相对位置反了！而我们又知道它俩的相对位置改不了，所以……完蛋了，肯定排不好了，喵 T^T。

2. 情况二：p[i] 比它应该在的位置上的数 i+1 小很多 (p[i] < i+1 且 |p[i] - (i+1)| >= 2)。

   • 此时，p[i] 在位置 i 上。而数字 i+1 肯定在 p[i] 的左边（某个下标 j < i 的地方）。
   • 所以，在初始排列里，i+1 在前，p[i] 在后。
   • 但是，因为 p[i] < i+1，在最终排好序的数组里，p[i] 应该在 i+1 的前面。
   • 初始顺序和目标顺序的相对位置又反了！它俩的相对位置还是改不了，所以……也排不好了，喵。

综上所述，我们得出了一个超级简单的判定方法： 遍历一遍输入的排列 p，对于每个位置 i（从0到n-1），检查 |p[i] - (i+1)| 是否大于等于 2。只要有任何一个位置满足这个条件，就说明无法排序，输出 "NO"。如果遍历完所有位置都没有发现这种情况，那就说明可以排序，输出 "YES"！

题解

这是根据上面的思路写出的 C++ 代码，非常简洁高效哦！

#include <iostream>
#include <vector>
#include <cmath>
#include <string>

// 这个函数处理单个测试用例的逻辑
void solve() {
    int n;
    std::cin >> n;
    bool is_possible = true; // 先乐观地假设可以排序，喵~

    // 我们可以一边读入数字一边处理，不需要把整个数组都存下来
    for (int i = 0; i < n; ++i) {
        int p_val;
        std::cin >> p_val;

        // 核心思想就是：当且仅当没有元素离它最终应该在的位置“太远”，排列才是可排序的。
        // 一个值为 v 的元素，最终应该在位置 v (1-indexed)。
        // 用 0-indexed 的话，一个在位置 i 的值 p_val，在排好序的数组里应该是 i+1。
        //
        // 可排序的条件是：对于所有的 i，|p[i] - (i+1)| < 2。
        // 这是因为一个元素 v 只能和 v-1、v+1 交换，意味着它不能“跨越”任何其他数字。
        // 这极大地限制了它从初始位置到最终位置的移动能力。
        // 如果一个元素与它的目标位置差了 2 或更多，就意味着它和某个数字之间存在无法解决的顺序冲突。
        
        // 我们为每个元素检查这个条件。如果任何时候这个条件被违反了，
        // 我们就把 is_possible 标志设为 false。
        if (std::abs(p_val - (i + 1)) >= 2) {
            is_possible = false;
        }
        
        // 注意！即使我们已经知道答案是 "NO" 了，也必须读完当前测试用例的所有 n 个整数，
        // 这样才不会影响下一个测试用例的输入流哦！
    }

    if (is_possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 在竞赛编程中用于提升性能的快速 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

1. 排列 (Permutation)

排列是组合数学里的一个基本概念。长度为 n 的排列，简单来说就是把 n 个不同的东西（比如数字1到n）按任意顺序排成一列。这是很多算法问题的基础设定，主人要熟悉哦。

2. 不变量 (Invariant)

这是解决这个问题的核心思想，也是一个非常强大的解题技巧！不变量是指在程序执行或一系列操作中，某个（或某些）属性始终保持不变。在这个问题里，我们发现**“任意两个数值差大于等于2的元素的相对顺序”**就是一个不变量。找到了不变量，常常能让复杂的问题瞬间简化。

3. 与冒泡排序的区别

这个问题里的交换操作很像冒泡排序，都是交换相邻元素。但它是一个受限制的版本。冒泡排序可以交换任意两个相邻元素，而这里加上了 |p_i - p_{i+1}| = 1 的苛刻条件，正是这个条件创造了上面说到的“不变量”，使得问题有了巧妙的解法。

希望我的讲解对主人有帮助！如果还有其他问题，随时可以再来找我哦，喵~ (´｡• ᵕ •｡`) ♡