В магазине есть товары, каждый задан ценой. У каждого покупателя есть
потребность — число. Покупатель берёт товар, ближайший по цене к своей
потребности; его неудовлетворённость — модуль разности между потребностью и
ценой купленного товара. Товаров каждого вида сколько угодно, один товар могут
купить многие. Верните суммарную неудовлетворённость всех покупателей.
// Dissatisfaction возвращает сумму |need - ближайший товар| по всем покупателям.
func Dissatisfaction(goods, needs []int) int
Примеры
goods=[2, 9, 6], needs=[6, 10] → 1 (6 берёт 6: 0; 10 берёт 9: 1)
goods=[5], needs=[1, 5, 8] → 7 (4 + 0 + 3)
goods=[1, 10], needs=[] → 0
Ограничения
1 ≤ len(goods) ≤ 2·10⁵, 0 ≤ len(needs) ≤ 2·10⁵, все числа по модулю
не больше 10⁹; goods не отсортированы, могут повторяться.- Входные слайсы не изменять.
- Перебор всех пар O(G·B) не проходит по времени.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.