Хорошо швейцарцами быть

да это довольно подготовительный год

Ребят, а можете дать идеи по решению задачи?

У нас есть два массива {a, b} одинаковой длины n и функция diff(a, b) = sum(|a[i]-b[i]|), i = 0, n -1.

Задача состоит в минимизация значения этой функции для заданных a, b, если можно заменить один любой эллемент массива a на другой эллемент этого же массива a.

Моё решение было создать массив tree, который будет содержать уникальные отсортированные эллементы a. Затем на каждом шаге брать idx = lower_bound (begin(tree), end(tre), b[i]) и таким образом выбрать наибольшую разницу, которую можно уменьшить, используя b[i] и соответствующие {tree[idx], tree[idx-1], a[i]}.

В итоге сложность O(n*log(n)). Можно ли как-то быстрее или проще?
Эллементы [-10^4, 10^4], колличество 10^5

Ну можно взять уникальные значения из массива a, из массива b, а потом посортировать подсчетом по отдельности. Потом слить функцией merge как в сортировке слиянием. В итоге вы за линию узнаете, какой элемент из массива a самый близкий к любому элементу из b. Но не сказал бы, что это проще

А не факт, что ближайший всегда будет правильным решением. ;)

Зачем сортировать, если есть сет?

Как предлагаешь применить сет?

я вижу «хранить уникальные, отсортированные» — это сет

А как задачу решать, понятия не имею)

std::set, если быть точным и речь о С++

Почему? Если я правильно понял, в задаче можно взять только один ai и заменить его на любой другой(в том числе оставить прежним). Значит мы меняем модуль разности |ai - bi|, а он тем меньше, чем ближе точка a к точке b. Поэтому можно найти для любого b ближайший a, и выбрать наилучший вариант

Там точно не перестановка? Если нет, то вы правы.

Да вроде там просто какой-то массив a целых чисел и какой-то массив b целых чисел, без доп. ограничений

Для a = [1, 1] и b = [1, 2] ответом будет a = [1, 1] и b = [1, 1]?

В задаче можно менять один элемент массива a, но вообще да)

diff(a, b) станет равным нулю, а это вообще наилучший возможный ответ, т.к. функция неотрицательна

Интереснее было бы, если перестановка

В каком смысле перестановка?

То есть элементы можно обменивать местами, но не копировать.

Только один?