C++ 数组的排列，该数组具有来自另一个数组的较小值

c++server side programmingprogramming

本教程中给出了两个数组 A 和 B。例如，我们需要输出 A 的任何排列，以便最大化 A[ I ] > B[ I ] 的索引，例如

输入:A = [12, 22, 41, 13],
B = [1, 20, 10, 12]
输出:12, 22, 41, 13
输入:A = [2, 5, 9, 7],
B = [1, 12, 4, 54]
输出:2 7 5 9
在这种情况下，可以存在多个答案，我们只需打印其中任何一个答案即可。

在这个问题中，我们需要最大化 A[ i ] > B[ i ] 的索引，所以我们将贪婪地解决这个问题。

寻找解决方案的方法

在这种方法中，我们现在将首先对两个数组进行排序；我们贪婪地检查数组 B 的每个索引，使得 A[ i ] 比它更重要，然后将该元素放入向量中。

示例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int A[] = { 2, 5, 9, 7 };
    int B[] = { 1, 12, 4, 54 };
    int n = sizeof(A) / sizeof(int); // 我们数组的大小
    vector<pair<int, int> > A_pair, B_pair;
    /***********************我们将元素链接到其位置***********/
    for (int i = 0; i < n; i++)
        A_pair.push_back({A[i], i});
    for (int i = 0; i < n; i++)
        B_pair.push_back({B[i], i});
    /****************************************************************************/
    /*****对我们的成对向量进行排序********************/
    sort(A_pair.begin(), A_pair.end());
    sort(B_pair.begin(), B_pair.end());
    int i = 0, j = 0, ans[n];
    memset(ans, -1, sizeof(ans)); // 用值 -1 初始化所有元素
    vector<int> remaining; // 这将存储比 B 中存在的元素值更小的元素。
    while (i < n && j < n) {
        //因为我们的数组是排序的，所以如果我们在
        //当前索引中找到任何元素，其值小于当前索引的 B，则
        //它会自动具有比 B 的其他元素更小的值
        //这就是为什么我们将这些索引推送到剩余部分，否则我们将元素推送到 ans
        if (A_pair[i].first > B_pair[j].first) {
              ans[B_pair[j].second] = A_pair[i].first;
            i++;
            j++;
          }
        else {
            remaining.push_back(i);
            i++;
        }
    }
    j = 0;
    for (int i = 0; i < n; ++i){
        //现在如果任何答案的索引不变，那么这意味着
        //我们需要用剩余的元素填充该位置
        if (ans[i] == -1){
            ans[i] = A_pair[remaining[j]].first;
            j++;
        }
    }
    for (int i = 0; i < n; i++) // 打印我们的答案
        cout << ans[i] << " ";
    return 0;
}

输出

2 7 5 9

上述代码的解释

在这种方法中，我们首先将所有元素链接到它们的索引，以便在对其进行排序时仍保留它们的旧索引。我们对两个成对的向量进行排序，现在我们在两个数组中移动时贪婪地搜索答案，如果我们得到的 A_pair 的索引比 B_pair 的索引具有更优值，那么我们将其存储在一个数组中(以及 B_pair 的位置)，否则因为我们已经对两个向量进行了排序，所以我们知道我们将无法使用 A_pair 的这个值，所以我们将该元素索引推送到我们剩余的向量中，现在我们借助剩余向量填充数组，然后打印答案。