Moe's CF Life

喵~ 主人好呀！今天由我，你最可爱的小猫娘，来为你讲解一道有趣的算法题，Codeforces 1638B - Odd Swap Sort。这道题就像是整理一堆毛线球，但有特殊的规则，很有意思的哦！一起来看看吧，喵~

题目大意

我们有一个数组 $a_1, a_2, \dots, a_n$ 。我们可以对这个数组进行一种特殊的操作：选择任意一个相邻的位置 $i$ （ $1 \le i < n$ ），如果 $a_i$ 和 $a_{i+1}$ 的和是奇数，我们就可以交换它们。

问题是：我们能通过任意次这样的操作，把整个数组变成非递减（也就是从小到大）的顺序吗？

举个例子，喵~

数组是 [1, 6, 31, 14]。我们可以交换 31 和 14，因为 31 + 14 = 45 是奇数。交换后数组变成 [1, 6, 14, 31]，它已经排好序啦！所以答案是 "Yes"。
数组是 [4, 2]。我们想把它变成 [2, 4]，就必须交换 4 和 2。但是 4 + 2 = 6 是偶数，不满足交换条件，所以我们什么都做不了。答案是 "No"。

题解方法

这道题的限制条件 a_i + a_{i+1} 是奇数，是解题的关键哦！主人你想想，两个整数相加，什么时候和是奇数呢？

挠挠头... 对啦！只有在一个数是奇数，另一个数是偶数的时候，它们的和才是奇数！

奇数 + 偶数 = 奇数
奇数 + 奇数 = 偶数
偶数 + 偶数 = 偶数

这意味着，我们只能交换相邻的一个奇数和一个偶数。我们 永远不能 交换两个相邻的奇数，也 永远不能 交换两个相邻的偶数。

这给我们一个非常重要的启示，喵！

所有奇数之间的相对顺序是永远不会改变的。
所有偶数之间的相对顺序也是永远不会改变的。

想象一下，我们把数组里所有的奇数按它们原来的顺序拿出来，排成一队，这就是“奇数子序列”。同样地，我们也可以得到一个“偶数子序列”。

比如说，对于数组 [2, 9, 6, 7, 10]：

奇数子序列是 [9, 7] （9 在 7 的前面）
偶数子序列是 [2, 6, 10] （2 在 6 前面，6 在 10 前面）

因为我们不能改变奇数内部的顺序，也不能改变偶数内部的顺序，所以，要想让整个数组最终有序，就必须满足两个条件：

奇数子序列本身已经是非递减的。
偶数子序列本身也已经是非递减的。

在上面的例子中，奇数子序列 [9, 7] 不是非递减的（9 > 7），所以无论我们怎么交换奇偶数，都不可能让 7 排到 9 的前面。因此，这个数组最终无法被排序。答案就是 "No"。

如果这两个子序列都各自有序，我们总能通过奇偶交换，把它们像拉拉链一样完美地合并成一个整体有序的数组。

所以，我们的算法就非常简单啦：

遍历一遍原数组。
把所有的奇数按原顺序放进一个列表，把所有的偶数按原顺序放进另一个列表。
检查奇数列表是不是已经排好序了。
检查偶数列表是不是也已经排好序了。
如果两个列表都排好序了，就输出 "Yes"，否则输出 "No"。

是不是很简单呢？喵~

题解

这是 C++ 的实现代码，我已经加上了可爱的注释，方便主人理解哦！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

/**
 * @brief 解决一个测试用例的函数喵~
 */
void solve() {
    int n;
    std::cin >> n;

    // 创建两个小篮子，一个放奇数，一个放偶数
    std::vector<int> odds;
    std::vector<int> evens;

    // 遍历整个数组，把数字按奇偶性分开装
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        if (val % 2 != 0) { // 如果是奇数
            odds.push_back(val);
        } else { // 如果是偶数
            evens.push_back(val);
        }
    }

    // 检查奇数的小篮子是不是已经排好序了
    bool odds_are_sorted = std::is_sorted(odds.begin(), odds.end());
    // 检查偶数的小篮子是不是也已经排好序了
    bool evens_are_sorted = std::is_sorted(evens.begin(), evens.end());

    // 如果两个篮子里的数字都乖乖排好队了，那就可以成功排序！
    if (odds_are_sorted && evens_are_sorted) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

int main() {
    // 这两行是为了让输入输出快一点，像小猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 有 t 组测试数据哦
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但涉及到的思想和工具都很有用哦！

奇偶性 (Parity) 这是整数的一个基本属性。一个数要么是奇数，要么是偶数。这个性质在很多数论和算法问题中都是突破口。记住奇偶数的加法规则是解开这道题的魔法钥匙哦，喵~
- 奇 + 偶 = 奇
- 奇 + 奇 = 偶
- 偶 + 偶 = 偶
子序列 (Subsequence) 子序列是指从一个序列中删除任意数量（可以为零）的元素，但保持剩下元素的相对顺序不变，所得到的新序列。比如 [A, C, D] 是 [A, B, C, D, E] 的一个子序列。在这道题里，我们实际上就是在考察原数组的“奇数子序列”和“偶数子序列”的有序性。这是一个很重要的抽象思维，把复杂的问题分解成更简单的子问题。
C++ STL std::is_sorted 这是 C++ 标准库 <algorithm> 头文件里的一个超级方便的函数。你给它一个范围（比如一个 vector 的开始和结束），它就能告诉你这个范围内的元素是不是已经按非递减顺序排好了。
- std::is_sorted(vec.begin(), vec.end()) 有了它，咱就不用自己写循环来检查啦，可以少写好多代码，多出时间来晒太阳了，的说！

好啦，今天的讲解就到这里啦！希望我的讲解对主人有帮助喵！如果还有不懂的地方，随时可以再来问我哦！下次再见啦！(ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍