Решение задачи Два массива и обмены с Codeforces
С пояснением   Просмотров: 203
Вам даны два массива a и b, оба состоят из n положительных (больших нуля) целых чисел. Также вам задано число k.
За один ход вы можете выбрать два индекса i и j (1≤i,j≤n) и поменять местами ai и bj (i.e. ai становится bj и наоборот). Заметьте, что i и j могут совпадать или отличаться (в частности, обмен a2 с b2 или обмен a3 с b9 оба считаются приемлемыми ходами).
Ваша задача — назвать максимальную возможную сумму, которую вы можете получить в массиве a, если вы сделаете не более k таких ходов (обменов).
Вам нужно ответить на t независимых наборов тестовых данных.
За один ход вы можете выбрать два индекса i и j (1≤i,j≤n) и поменять местами ai и bj (i.e. ai становится bj и наоборот). Заметьте, что i и j могут совпадать или отличаться (в частности, обмен a2 с b2 или обмен a3 с b9 оба считаются приемлемыми ходами).
Ваша задача — назвать максимальную возможную сумму, которую вы можете получить в массиве a, если вы сделаете не более k таких ходов (обменов).
Вам нужно ответить на t независимых наборов тестовых данных.
Пояснение к задаче
Во время каждого хода мы можем брать минимальный элемент в a, максимальный элемент в b и поменять их (если минимум в a меньше, чем максимум в b). Если мы повторим эту операцию k раз, то мы получим ответ. Это можно сделать за O(n * n * n), O(n * n), но авторское решение работает за O(nlogn).