Расположение массивов так, чтобы максимальное количество элементов было больше в одном массиве

Question

Предполагая, что у меня есть два массива A и B (оба с равным количеством элементов)

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

Я должен переставить массив A таким образом, чтобы максимальное количество элементов в массиве A было больше, чем их соответствующие элементы в массиве B.

В этом случае перестановка A в {40,70,50} даст требуемый результат.

Каков наиболее оптимальный путь для этого?

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).

Answer 2

Предположим, что мы также можем переставить B на данный момент. Ясно, что всегда оптимально сопоставлять самые большие элементы в A с меньшими элементами в B. Поэтому мы можем перебирать элементы в A в порядке убывания и пытаться соединить их с меньшими элементами в B.

Для каждого элемента в A мы хотим использовать самый большой неиспользуемый элемент в B, который меньше, чем элемент в A, поскольку мы хотим сохранить меньшие элементы в B для использования позже. Мы можем отсортировать B и найти этот элемент, используя бинарный поиск или поддерживая указатель на самый большой неиспользуемый элемент. Если в какой-то момент мы не сможем найти неиспользуемый элемент в B, который меньше, чем следующий элемент в A, мы знаем, что мы не сможем сопоставить остальные элементы в A с меньшими элементами в B, поэтому мы можем сопоставьте оставшиеся элементы произвольно. Теперь мы можем переставить пары так, чтобы элементы в B были в их первоначальном порядке, и у нас есть решение.