题目分析

核心问题：给定一个由 1 到 n 组成的排列，我们可以交换任意两个互质的数字。问是否能通过一系列这样的交换，将这个排列从小到大排序。

关键概念

排列：序列包含 1 到 n 的每个整数，且只出现一次。 互质：两个数的最大公约数（gcd）为 1。例如，5 和 8 互质（gcd (5,8)=1），而 4 和 6 不互质（gcd (4,6)=2）。 交换操作：我们只能交换一对互质的数。 思路分析 要解决这个问题，我们需要找到一种策略，通过合法的交换（交换互质数）来移动任意一个元素到它应该在的位置。

核心洞察

数字 1 是解题的关键。 1 的性质：数字 1 和任何正整数都互质。这意味着 1 可以和排列中的任何其他数字进行交换。 1 的作用：如果 1 已经在它正确的位置（即数组的第一个位置 a[0]），那么我们就可以用它作为一个 “中转站” 来移动其他任何数字。 让我们看看如何利用 1 作为中转站：假设我们想交换两个不互质的数，比如 x 和 y，并且它们都不等于 1。 将 x 和 1 交换。（因为 gcd(x, 1) = 1，合法） 将 1 和 y 交换。（因为 gcd(1, y) = 1，合法） 将 x（现在在 1 的原位置）和 1（现在在 y 的原位置）交换。（因为 gcd(x, 1) = 1，合法） 经过这三步，我们成功地交换了 x 和 y 的位置，尽管它们本身不互质。 结论：如果数字 1 已经在正确的位置（即 a[0] == 1），那么我们可以通过上述方法交换任意两个数。这意味着我们拥有了完全的排序能力，可以对整个数组进行排序。因此，答案是 Yes。 那如果 1 不在正确的位置呢？在这种情况下，我们的交换能力是有限的。我们不能随意交换任何两个数。 1 的移动：要将 1 移动到正确的位置，我们必须找到一个和它互质的数，并且这个数正好在 1 应该在的位置上。 简化问题：当 1 不在正确位置时，我们可以简化判断条件。因为我们不能自由交换，所以排序的条件变得非常苛刻。一个必要条件是：对于所有大于 1 的数 i，它必须已经在它的正确位置 i-1 上。 为什么？因为如果有一个数 k (k> 1) 不在它的正确位置，那么要移动它，我们很可能需要借助 1 或者与它互质的数。但由于 1 本身也错位了，整个系统的交换能力受到限制。唯一能保证成功排序的简单情况就是除了 1 之外，其他所有数都已经排好序了。 所以，当 1 不在 a[0] 时，我们只需要检查从 a[1] 到 a[n-1] 的所有元素是否都满足 a[i] == i + 1。如果满足，答案是 Yes；否则，答案是 No。

算法设计

读取输入：读取排列的长度 n 和排列 a。 检查 1 的位置： 情况 A：如果 a[0] == 1：我们可以自由交换任何元素，因此一定可以排序。直接输出 Yes。 情况 B：如果 a[0] != 1：我们的交换能力受限。此时，我们需要检查数组中除了第一个元素之外的所有其他元素是否都已经在正确的位置上。 遍历数组，从索引 i = 1 到 i = n - 1。 检查对于每个 i，是否都满足 a[i] == i + 1。 如果所有位置都满足这个条件，输出 Yes。 如果有任何一个位置不满足，输出 No。 C++ 代码实现:****

#include <iostream>
#include <vector>

int main() {
    // 提高C++ I/O效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 如果 1 已经在正确的位置 a[0]
    if (a[0] == 1) {
        std::cout << "Yes\n";
    } else {
        // 1 不在正确位置，需要检查其他所有元素是否都已就位
        bool is_possible = true;
        for (int i = 1; i < n; ++i) {
            // 对于索引 i，正确的数字应该是 i + 1
            if (a[i] != i + 1) {
                is_possible = false;
                // 找到一个不匹配的就可以提前退出循环
                break;
            }
        }

        if (is_possible) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

代码解释

#include <...>：包含了标准输入输出流和动态数组 vector 所需的头文件。 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);：这是竞赛编程中常用的优化，用于加速 cin 和 cout。 读取数据：代码首先读取排列的长度 n，然后读取整个排列到 vector a 中。 核心逻辑判断： if (a[0] == 1)：这是最关键的判断。如果 1 在第一位，我们直接输出 "Yes"。 else 块处理 1 不在第一位的复杂情况。 在 else 块中，我们假设排序是可能的 (is_possible = true)，然后通过一个 for 循环去验证这个假设。 循环从 i = 1 开始，检查 a[i] 是否等于它应该在的值 i + 1。 如果发现任何一个位置不匹配 (a[i] != i + 1)，我们就将 is_possible 设为 false 并 break 循环，因为已经可以确定无法排序了。 循环结束后，根据 is_possible 的最终值输出 "Yes" 或 "No"。 这个算法的时间复杂度是 O(n)，空间复杂度是 O(n)（用于存储输入的数组），完全可以满足题目 n ≤ 10^5 的要求。