Уравнять сумму в двух массивах, сделав одну перестановку
Имеются два массива. Необходимо выбрать по одному элементу из каждого массива и поменять их местами так, чтобы сумма в массивах стала одинаковой. Подскажите каким образом можно реализовать алгоритм для решения задачи (Осуществил наивную реализацию с перебором элементов, но при большом количестве элементов массива будет очень долго выполняться)
Ответы (2 шт):
Любая пара элементов, разница между которыми равна половине разницы между суммами. Разница элементов с правильным знаком, конечно, - тем же, что и разница сумм.
Мы знаем, что для двух массивов {a} и {b} нужно выбрать такие элементы a' и b', что a' = b' + (Sa-Sb)/2, где Sa и Sb - суммы. Чтобы работать быстро, можем поместить элементы в set или, еще быстрее, unordered_set.
Пусть для определенности set - тогда размещение элементов - O(n*log(n)+m*log(m)) (n и m - размеры множеств). Далее проход по одному множеству, что покороче, и поиск, есть ли во втором такой элемент - O(n*log(m)) или O(m*log(n)). Пусть для определенности n меньше m. Таким образом, сложность всей задачи -
O(n*log(n)+m*log(m)+n*log(m))
Не так и много. Для unordered_set и того быстрее.
Ну и, понятно, если разность сумм нечетная - то можно и не возиться :)