Код Senior Бинарный поиск обновлено
Суммарная неудовлетворённость
Условие
Массив товаров (числа) и массив потребностей покупателей (числа). Покупатель берёт ближайший по значению товар; неудовлетворённость - модуль разницы. Товары не кончаются. Верни сумму неудовлетворённостей.
Примеры
totalDissatisfaction([8, 3, 5], [5, 6]) // 1
totalDissatisfaction([8, 3, 5], [5, 10]) // 2
totalDissatisfaction([1], [100]) // 99
Как подойти
Сортировка O(n log n) плюс O(m log n) на запросы вместо наивных O(n·m). Ключевая деталь, которую забывают: lowerBound даёт первый элемент не меньше нужного, но ближайшим может оказаться предыдущий - сравнивать надо обоих соседей. Infinity как заглушка для отсутствующего соседа избавляет от ветвлений по границам.
Подсказки: 3
- Отсортируй товары один раз, дальше по каждому запросу - бинарный поиск.
- Ближайший может быть как справа от точки вставки, так и слева - проверь оба соседа.
- Пустой список товаров - отдельный случай.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.