构造 - 题解

标签与难度

标签: 构造, 思维, 贪心, 排列, 前缀和

难度: 1400

题目大意喵~

主人你好呀，这道题是要我们当一回小小建筑师呢，喵~

题目会给我们三个数字 $n, a, b$。我们的任务是构造一个长度为 $2n$ 的排列 $P$，也就是一个包含 $1$ 到 $2n$ 所有数字、每个数字只出现一次的序列。

这个排列 $P$ 需要满足两个神奇的条件哦：

1. 在排列的指定位置 $a$ 上，必须放上数字 $b$。也就是 $P_a = b$。
2. 对于任何一个分割点 $i$（从 $1$ 到 $2n-1$），排列前 $i$ 个数的和（我们叫它前缀和 $pre_i$）不能等于后 $i$ 个数的和（我们叫它后缀和 $suf_i$）。也就是 $\forall 1 \le i < 2n, pre_i \neq suf_i$。

题目保证一定有解，所以我们大胆去构造就好啦！

举个栗子：如果 $n=2, a=2, b=4$，我们需要构造一个长度为 $4$ 的排列。一个可能的答案是 2 4 1 3。这里 $P_2=4$ 满足了第一个条件。我们还要检查第二个条件：

• $i=1$: 前1项和是 $2$，后1项和是 $3$。$2 \neq 3$，通过！
• $i=2$: 前2项和是 $2+4=6$，后2项和是 $1+3=4$。$6 \neq 4$，通过！
• $i=3$: 前3项和是 $2+4+1=7$，后3项和是 $4+1+3=8$。$7 \neq 8$，通过！

所有条件都满足，所以这是一个正确的答案，喵~

解题思路分析

这道题最棘手的部分就是那个不等式条件 $pre_i \neq suf_i$ 啦。要对所有的 $i$ 都满足，一个个去凑也太麻烦了，我的猫爪都要挠秃了！(>ω<)

所以，我们得想个聪明的办法，从根本上解决这个问题。

不等式 $pre_i \neq suf_i$ 看起来有点弱，不如我们来满足一个更强的条件，让它自然成立？比如说，我们能不能构造一个排列，让前缀和总是小于后缀和（或者总是大于后缀和）呢？

寻找安全的“模板”排列

怎么才能让前缀和总是比后缀和有规律地大或者小呢？最简单的方法就是让排列本身有序！

模板一：升序排列 如果我们构造一个升序排列 P_inc = [1, 2, 3, ..., 2n]。

• $pre_i$ 就是前 $i$ 个最小的数的和。
• $suf_i$ 就是后 $i$ 个最大的数的和。 用脚爪想想都知道，对于任何 $i < 2n$，一堆最小的数加起来，肯定比一堆最大的数加起来要小嘛！所以，对于这个排列，我们能保证 $pre_i < suf_i$ 恒成立。

模板二：降序排列 反过来，如果我们构造一个降序排列 P_dec = [2n, 2n-1, ..., 1]。

• $pre_i$ 就是前 $i$ 个最大的数的和。
• $suf_i$ 就是后 $i$ 个最小的数的和。 这样一来，我们就能保证 $pre_i > suf_i$ 恒成立啦！

太棒了！我们找到了两个“安全”的模板，它们本身就满足了第二个条件。现在我们只需要在这些模板上稍作修改，来满足第一个条件 $P_a=b$ 就好啦。

如何选择模板并进行修改？

我们的目标是把数字 $b$ 放到位置 $a$ 上。最简单的修改方式就是进行一次交换。

但是，我们应该选择哪个模板呢？升序还是降序？ 这里的诀窍是：选择一个与我们目标 (在位置 a 放 b) “气质”最相符的模板，这样修改时对原有结构的破坏最小，就能保住 $pre_i \neq suf_i$ 的好性质，喵~

我们把 $1$ 到 $n$ 的索引和数值看作“小”的一半，把 $n+1$ 到 $2n$ 的看作“大”的一半。

1. 升序模板 P_inc 的气质：小数值配小索引，大数值配大索引。
2. 降序模板 P_dec 的气质：大数值配小索引，小数值配大索引。

现在我们来看看我们的任务 P_a = b：

情况一：a 和 b "同侧"

• 当 a 和 b 都是“小”的 ($a \le n$ 并且 $b \le n$)
• 或者 a 和 b 都是“大”的 ($a > n$ 并且 $b > n$)

这种任务的气质是“小配小”或“大配大”，这和升序模板 P_inc 的气质完美契合！所以我们选择 P_inc。 在 P_inc = [1, 2, ..., 2n] 中，数字 $b$ 本来在位置 $b$。我们只需要交换位置 $a$ 和位置 $b$ 上的数，就能把 $b$ 请到位置 $a$ 上去啦。因为我们交换的两个数要么都在“小”的那半边，要么都在“大”的那半边，对整个排列“小值在前，大值在后”的大格局影响不大，所以 $pre_i < suf_i$ 的性质依然能保持。

情况二：a 和 b "异侧"

• 当 a 是“小”的而 b 是“大”的 ($a \le n$ 并且 $b > n$)
• 或者 a 是“大”的而 b 是“小”的 ($a > n$ 并且 $b \le n$)

这种任务的气质是“大配小”或“小配大”，这不就和降序模板 P_dec 的气质一模一样嘛！所以我们选择 P_dec。 在 P_dec = [2n, 2n-1, ..., 1] 中，我们想把 $b$ 放到位置 $a$。首先得找到 $b$ 在哪儿。对于一个值 $k$，它在 P_dec 中的位置是 $2n - k + 1$。所以 $b$ 在位置 $2n - b + 1$。我们只需要交换位置 $a$ 和位置 $2n - b + 1$ 上的数，就可以啦。同样，这种交换是顺应了 P_dec 的大趋势，不太可能破坏 $pre_i > suf_i$ 的性质。

总结一下我们的策略：

1. 判断 a 和 b 是同侧还是异侧。
   • 如果 (a <= n && b <= n) || (a > n && b > n)，它们是同侧。
   • 否则，它们是异侧。
2. 同侧：
   • 生成升序排列 P = [1, 2, ..., 2n]。
   • 为了实现 P_a = b，我们交换 P_a 和 P_b。
3. 异侧：
   • 生成降序排列 P = [2n, 2n-1, ..., 1]。
   • 在 P 中，值为 b 的元素在第 2n - b + 1 个位置。
   • 为了实现 P_a = b，我们交换 P_a 和 P_{2n - b + 1}。

这样，我们就能轻松构造出满足所有条件的排列了，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~

#include <iostream>
#include <vector>
#include <numeric>   // 为了 std::iota
#include <algorithm> // 为了 std::swap 和 std::reverse

// 一个乐于助人的函数，用来解决单次询问
void solve() {
    int n, a, b;
    std::cin >> n >> a >> b;

    std::vector<int> p(2 * n);

    // 判断 a 和 b 是不是在 "同一侧"
    // "小"的一半是 <= n, "大"的一半是 > n
    bool same_side = (a <= n && b <= n) || (a > n && b > n);

    if (same_side) {
        // 情况一：a 和 b 同侧，使用升序模板
        // P = [1, 2, 3, ..., 2n]
        std::iota(p.begin(), p.end(), 1);

        // 为了让 p[a-1] == b (注意C++是0-indexed),
        // 我们需要把原本在 p[a-1] 的数 (也就是 a)
        // 和原本在 p[b-1] 的数 (也就是 b) 进行交换
        std::swap(p[a - 1], p[b - 1]);

    } else {
        // 情况二：a 和 b 异侧，使用降序模板
        // P = [2n, 2n-1, ..., 1]
        std::iota(p.begin(), p.end(), 1);
        std::reverse(p.begin(), p.end());

        // 为了让 p[a-1] == b, 我们需要找到 b 在哪儿
        // 在降序排列中, 数字 k 在索引 2n-k 的位置
        // 所以数字 b 在索引 2n-b 的位置
        int b_original_idx = 2 * n - b;

        // 交换 p[a-1] 和 p[b_original_idx] 上的数
        std::swap(p[a - 1], p[b_original_idx]);
    }

    // 优雅地输出结果~
    for (int i = 0; i < 2 * n; ++i) {
        std::cout << p[i] << (i == 2 * n - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 对于每个测试用例，我们做的操作有：

  1. 生成一个长度为 $2n$ 的排列，使用 std::iota 是 $O(N)$。
  2. 如果需要，std::reverse 也是 $O(N)$。
  3. 交换两个元素是 $O(1)$。
  4. 最后输出排列是 $O(N)$。 所以总的时间复杂度是 $O(N)$ 呐。

• 空间复杂度: $O(N)$ 我们需要一个 std::vector 来存储长度为 $2n$ 的排列，所以占用的额外空间是 $O(N)$ 的说。

知识点总结

这道题虽然是构造题，但核心思想非常精妙，我们可以从中学到不少东西，喵~

1. 问题简化: 面对一个复杂的约束条件（比如 !=），可以尝试用一个更强的、但更容易处理的条件（比如 < 或 >) 来代替它。这是一种非常重要的解题策略！
2. 构造思想: 许多构造题的解法是先建立一个满足大部分条件的“基础模板”，然后再对这个模板进行微调，以满足剩下的特殊条件。
3. 分类讨论: 根据输入参数的性质（本题中是 a 和 b 的相对大小）进行分类讨论，为不同情况选择最优的策略，是解决复杂问题的常用方法。
4. 排列性质: 熟悉升序/降序排列的性质，尤其是它们的前后缀和特性，可以为构造提供灵感。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！一起加油，喵~ 🐾