安排数组使得一个数组中的最大元素数量最多

Question

假设我有两个数组 A 和 B（长度相同）:

int A[] = {40,50,70};
int B[] = {80,60,45};

我需要重新排列数组A，使得数组A中比数组B中对应元素大的元素数量最大。

在这种情况下，将A重新排列为{40,70,50}将产生所需的结果。

如何以最优的方式实现此目标？

- Bharath Suresh

---

你目前尝试了什么？展示一下你的尝试，也许这里的某个人会提供一种��复或改进你代码的方法。 - Adrian Mole

从你能想到的最佳方法开始。将其写下来。运行它。速度够快吗？如果不够快，寻找可用于减少所需执行工作量的模式。在你的方法被证明过慢之前，不必担心最优化。 - user4581301

@pmg 是的，我们可以对它们进行排序。 - Bharath Suresh

@PaulMcKenzie：没有大于80的值，而且40比45小。 - Jarod42

从A中取出较大的值，将其放置在小于该值的最大值处。重复此过程，直到所有剩余的A值都太小，将剩余的任意排列。 - Jarod42

Answer 1

我会使用类似以下的内容：

std::vector<int> f(std::vector<int> A, const std::vector<int>& B)
{
    std::vector<std::size_t> indexes(B.size());
    std::iota(indexes.begin(), indexes.end(), 0);

    std::sort(A.begin(), A.end(), std::greater<>{});
    std::sort(indexes.begin(), indexes.end(),
              [&B](std::size_t lhs, std::size_t rhs){ return B[lhs] > B[rhs]; });

    auto it = A.begin();
    auto rit = A.rbegin();
    std::vector<int> res(A.size());
    for (auto index : indexes) {
        if (*it > B[index]) {
            res[index] = *it;
            ++it;
        } else {
            res[index] = *rit;
            ++rit;
        }
    }
    return res;
}

演示

复杂度：O(n log n)。

- Jarod42

---

我做了你在评论中提到的类似的事情。它起作用了。但这更有效率。 - Bharath Suresh

Answer 2

假设我们现在也可以重新排列B。显然，将A中最大的元素与B中较小的元素匹配始终是最优的。因此，我们可以按照递减顺序迭代A中的元素，并尝试将它们与B中较小的元素配对。

对于A中的每个元素，我们希望使用B中最大的未使用元素，该元素小于A中的元素，因为我们希望将B中较小的元素留到后面使用。我们可以对B进行排序，并使用二分查找或通过维护指向最大未使用元素的指针来找到这个元素。如果我们无法找到一个未使用的B元素，该元素小于A中的下一个元素，则我们知道我们将无法将A中的其余元素与B中较小的元素匹配，因此我们可以任意匹配剩余的元素。现在，我们可以重新排列这些配对，使得B中的元素保持原始顺序，从而得到一个解决方案。

- eesiraed