Moe's CF Life

喵~ 主人，欢迎来到我的题解小课堂！今天我们要看的是一道关于数组和排列的有趣问题，Codeforces 上的 1867A 题。别担心，这道题其实很简单的说，跟着我的思路一步步来，很快就能明白啦！

题目大意

这道题是这样子的，喵~

我们有一个长度为 n 的数组 a。我们的任务是，找到一个长度也为 n 的排列 b。

什么是排列喵？一个长度为 n 的排列，就是一个包含了从 1 到 n 这 n 个不同整数的数组，顺序可以任意。比如 [2, 3, 1] 就是一个长度为 3 的排列。

然后，我们会计算一个“逐元素差值”数组 c，其中 c_i = a_i - b_i。

我们的最终目标是：让我们构造的排列 b，能够使得差值数组 c 中不同数字的数量达到最大。

最后，把我们找到的这个排列 b 输出出来就可以啦~

题解方法

想让 c 数组里不同数字的数量最多，最多能有多少个呢？因为 c 的长度是 n，所以最多也就有 n 个不同的数字，对不对喵？所以，我们的目标就是让所有的 c_i = a_i - b_i 互不相同！

怎么才能做到呢？这里就要用上我们猫咪的智慧了，喵~ 我们可以用贪心算法来解决！

你想想看，数组 a 里的数字可能很大，也可能很小，还可能重复。而排列 b 里的数字是固定的 1, 2, ..., n。为了让差值 a_i - b_i 尽可能地分散开，一个很自然的想法就是：

用 a 中最大的数，去减 b 中最小的数 (也就是 1)。
用 a 中第二大的数，去减 b 中第二小的数 (也就是 2)。
... 以此类推 ...
用 a 中最小的数，去减 b 中最大的数 (也就是 n)。

这样一来，大的减小的，差值就很大；小的减大的，差值就很小（甚至是负数）。直觉上这样操作，差值之间会拉得很开，就不容易重复了。

我们来简单证明一下这个策略为什么总是正确的哦。假设我们有两个 a 中的元素 a_x 和 a_y，它们在原数组中的下标分别是 x 和 y。不妨设 a_x >= a_y。根据我们的贪心策略，a_x 会被分配一个较小的 b 值，而 a_y 会被分配一个较大的 b 值。也就是说 b_x < b_y。那么它们的差值分别是 c_x = a_x - b_x 和 c_y = a_y - b_y。因为 a_x >= a_y 且 b_x < b_y (这意味着 -b_x > -b_y)，所以 a_x - b_x > a_y - b_y 是一定成立的！看吧，只要 a 中的两个值不完全相等，它们的差值就肯定不会相等。如果 a 中有两个值相等，比如 a_x = a_y，那么它们会被分配不同的 b 值 (b_x 和 b_y)，所以差值也必然不同。因此，这个策略可以保证我们得到 n 个完全不同的差值，达到了最大可能数量！

具体实现步骤：

我们不能直接对数组 a 进行排序，因为这样会丢失每个元素原来的位置。
所以，我们可以创建一个新的结构，比如 C++ 中的 std::vector<std::pair<int, int>>。每个 pair 存储 (a_i 的值, a_i 的原始下标 i)。
对这个 pair 数组按照值进行降序排序（从大到小）。
创建一个结果数组 b，大小为 n。
遍历排好序的 pair 数组。对于第 i 个 pair（也就是第 i 大的元素），我们取出它保存的原始下标 original_idx，然后在 b[original_idx] 的位置上填入 i+1。
这样，a 中最大的元素对应的 b 值是 1，第二大的元素对应的 b 值是 2，...，最小的元素对应的 b 值是 n。
最后输出数组 b 就大功告成啦！

题解

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

cpp

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

// 处理单个测试用例的函数喵~
void solve() {
    int n;
    std::cin >> n;
    
    // 创建一个 vector，里面放 pair 哦。
    // pair 的第一个元素存 a 的值，第二个元素存它原来的位置（下标）。
    // 这样排序后就不会找不到家了喵~
    std::vector<std::pair<int, int>> a_pairs(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a_pairs[i].first;  // 读取 a_i 的值
        a_pairs[i].second = i;         // 记录原始下标 i
    }
    
    // 这里是关键！我们把 a_pairs 从大到小排序。
    // `rbegin()` 和 `rend()` 是反向迭代器，可以方便地实现降序排序，很方便的说！
    std::sort(a_pairs.rbegin(), a_pairs.rend());
    
    // 创建要输出的排列 b
    std::vector<int> b(n);
    
    // 遍历排好序的 a_pairs
    for (int i = 0; i < n; ++i) {
        // 排好序之后，第 i 个 pair (从0开始数) 就是第 i+1 大的数啦。
        // 我们把它对应的 b 值（也就是 i + 1）填回到 b 数组里。
        // 填在哪里呢？就填在我们之前存好的原始下标 a_pairs[i].second 的位置上，喵~
        b[a_pairs[i].second] = i + 1;
    }
    
    // 把我们精心构造的排列 b 输出出来
    for (int i = 0; i < n; ++i) {
        std::cout << b[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; // 读取测试用例的数量
    while (t--) {
        solve();
    }
    
    return 0;
}

知识点介绍

这道题虽然简单，但涉及到的知识点可是很核心的哦！

排列 (Permutation) 排列是组合数学中的一个基本概念。简单来说，一个长度为 n 的排列就是把 1, 2, ..., n 这 n 个数字不重复、不遗漏地排成一列。就像把 n 只不同花色的小猫排成一队，每只小猫都要上场，且只能上场一次，就是这个意思喵~
贪心算法 (Greedy Algorithm) 贪心算法是一种非常直观的算法思想。它在每一步决策时，都采取当前状态下最好或最优的选择，期望通过一系列的局部最优解，最终能得到全局最优解。就像小猫看到面前有两条路，一条路上有小鱼干，另一条没有，那肯定先走有小鱼干的路啦！这道题里，我们每一步都将“当前 a 中最大的数”和“当前 b 中最小的数”配对，这是一个局部最优选择，而事实证明它也导向了全局最优解，真棒喵！
排序与 pair (Sorting with pair) 在算法题中，我们经常需要对数据进行排序，但又不想丢失数据附带的其他信息（比如原始的下标）。这时候，把数值和附加信息打包成一个 std::pair (在 C++ 中) 或者一个自定义的结构体，是一个超级好用的技巧！std::pair 和 std::sort 配合起来简直是天作之合，能轻松解决这类问题，主人一定要熟练掌握哦~

希望这个题解能帮到你哦，如果还有不懂的地方，随时可以再来问我，喵~ ❤️

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍