喵~ Codeforces 1831A - Twin Permutations 题解来啦！

哈喽，各位主人！今天本喵要给大家带来一道非常有趣的构造题的题解哦，nya~ 这道题就像是给两只小猫配对，要让它们加起来的“可爱值”排排站好，是不是很可爱呢？

题目大意喵~

这道题是这样哒：

我们有一个长度为 n 的排列 a。排列 a 里面装着从 1 到 n 这 n 个不同的数字，只是顺序被打乱了而已，喵。

我们的任务是，找到另一个长度为 n 的排列 b，也要包含从 1 到 n 这 n 个不同的数字。这个排列 b 需要满足一个特殊的条件：

a₁ + b₁ ≤ a₂ + b₂ ≤ a₃ + b₃ ≤ … ≤ aₙ + bₙ

也就是说，a 和 b 在相同位置上的元素相加，得到的 n 个和必须是一个 非递减 的序列（就是说后面的和不能比前面的小，可以相等哦）。

题目保证一定能找到这样的排列 b，所以我们只要随便找一个符合条件的就好啦！

举个例子，如果 a = [1, 2, 4, 5, 3]，我们可以找到 b = [1, 2, 4, 3, 5]。你看，它们的和是：

a₁ + b₁ = 1 + 1 = 2
a₂ + b₂ = 2 + 2 = 4
a₃ + b₃ = 4 + 4 = 8
a₄ + b₄ = 5 + 3 = 8
a₅ + b₅ = 3 + 5 = 8

这个和序列 [2, 4, 8, 8, 8] 就是一个非递减序列，所以这个 b 就是一个合格的答案，喵~

解题思路喵！

看到这种 ≤ 连接的不等式链，是不是有点头大呀？别怕别怕，本喵教你一个超级简单的思考方法！

要让一个序列是非递减的，最简单粗暴的方法是什么呢？就是让序列里所有的数都相等嘛！如果所有的 aᵢ + bᵢ 都等于同一个常数 C，那 C ≤ C ≤ ... ≤ C 这个条件不就轻轻松松满足了吗？嘻嘻~

好！那我们就朝着这个方向努力！

我们的目标是：对于所有的 i (从 1 到 n)，都满足 aᵢ + bᵢ = C。

把这个式子变个形，我们就能得到 bᵢ 的计算公式啦：

bᵢ = C - aᵢ

现在问题就变成了：这个神秘的常数 C 到底应该是多少呢？

别忘了，b 也是一个从 1 到 n 的排列哦。这意味着 {b₁, b₂, ..., bₙ} 这个集合必须等于 {1, 2, ..., n} 这个集合。

我们把 bᵢ 的公式代进去，也就是说 {C - a₁, C - a₂, ..., C - aₙ} 这个集合必须等于 {1, 2, ..., n}。

因为 a 本身也是一个从 1 到 n 的排列，所以 {a₁, a₂, ..., aₙ} 这个集合也正好是 {1, 2, ..., n}。

那么，{C - aᵢ} 这个集合，其实就等价于 {C - 1, C - 2, ..., C - n} 这个集合（只是顺序不一样而已）。

为了让 {C - 1, C - 2, ..., C - n} 和 {1, 2, ..., n} 这两个集合完全一样，我们只需要让它们的最小值和最大值对应上就可以啦！

集合 {1, 2, ..., n} 的最小值是 1，最大值是 n。
集合 {C - 1, C - 2, ..., C - n} 的最小值是 C - n，最大值是 C - 1。

所以我们得到：

最小值相等： C - n = 1
最大值相等： C - 1 = n

从这两个方程里，我们都能解出 C = n + 1！

哇！我们找到 C 了！所以，构造 b 的完美公式就是：

bᵢ = (n + 1) - aᵢ

我们来验证一下这个方法是不是真的万无一失，喵~

bᵢ 是不是在 1 到 n 的范围里？ 因为 1 ≤ aᵢ ≤ n，所以 (n + 1) - n ≤ (n + 1) - aᵢ ≤ (n + 1) - 1，化简一下就是 1 ≤ bᵢ ≤ n。完美！
bᵢ 是不是互不相同？ 如果 aᵢ ≠ aⱼ，那么 (n + 1) - aᵢ ≠ (n + 1) - aⱼ，所以 bᵢ ≠ bⱼ。也完美！
aᵢ + bᵢ 是不是非递减？aᵢ + bᵢ = aᵢ + ((n + 1) - aᵢ) = n + 1。所有的和都是 n + 1，当然是非递减的啦！

所以，这个方法是完全正确的！我们只需要遍历输入的 a 数组，对于每一个 aᵢ，计算出 (n + 1) - aᵢ 并输出，就解决问题啦！是不是超级简单，nya~

AC代码喵~

这是可以直接提交通过的C++代码哦，主人可以参考一下~

cpp

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

// 解决单个测试用例的函数喵
void solve() {
    int n;
    std::cin >> n;
    
    // 我们不需要真的把 a 数组存起来，可以一边读一边处理，更省空间哦
    for (int i = 0; i < n; ++i) {
        int a_i;
        std::cin >> a_i;
        // 根据我们的公式 b_i = (n + 1) - a_i 直接输出 b_i
        std::cout << (n + 1) - a_i << (i == n - 1 ? "" : " ");
    }
    std::cout << "\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;
}

知识点小课堂喵~

什么是排列 (Permutation) 呀？

排列，就是一个包含了从 1 到 n 这 n 个不同整数的数组，顺序可以随便打乱。

比如说，n=4 的时候：

[1, 2, 3, 4] 是一个排列。
[4, 2, 1, 3] 也是一个排列。
[1, 2, 2, 3] 不是排列，因为 2 出现了两次，数字不唯一了喵。
[1, 2, 4] 不是排列，因为它长度不够，而且 n=3 却出现了 4 也不对。

简单说，就是把 1 到 n 这些数字拿来排队，每种排法都是一个排列！

什么是构造算法 (Constructive Algorithm) 呀？

构造算法问题，通常不会问你“最优解”或者“唯一解”，而是让你“找到任意一个满足条件的解”。

解决这类问题的关键，往往不是复杂的算法，而是找到一个简单、普适的 构造规律。就像我们这道题一样，我们没有去尝试各种复杂的 b，而是想到了一个最简单的规律——“让所有和都相等”。

这个“将变量转化为常量”的思路，在很多构造题里都非常有用哦！当你遇到一个要求满足某种大小关系（比如非递减、非递增）的构造题时，不妨先想一想：能不能让它们全都相等呢？这常常会是通往正确答案的捷径，喵~

好啦，今天的题解就到这里啦！希望对主人有帮助！下次再见，喵~ (ฅ'ω'ฅ)

喵~ Codeforces 1831A - Twin Permutations 题解来啦！ ​

题目大意喵~ ​

解题思路喵！ ​

AC代码喵~ ​

知识点小课堂喵~ ​

什么是排列 (Permutation) 呀？ ​

什么是构造算法 (Constructive Algorithm) 呀？ ​