MiddleКодРедкоЕщё не отвечали
Суммарная неудовлетворённость покупателей по ближайшим товарам
goods содержит значения доступных товаров (каждого неограниченно). Каждый покупатель в needs берёт товар, ближайший к его потребности; неудовлетворённость — abs(need - chosen). Верните суммарную неудовлетворённость по всем покупателям.
Требования:
- O(n log n) время; обгоните перебор O(n*m).
- Пример:
goods=[8,3,5], needs=[5,6]->1.
def total_dissatisfaction(goods, needs):
# ваш код здесьДопишите реализацию.
Отсортируйте goods один раз, затем для каждой потребности найдите точку вставки через bisect_left и сравните соседа снизу и сверху, взяв меньшее расстояние abs. Сумма даёт ответ за O((n+m) log n). Перебор — проход по всем товарам на покупателя — это O(n*m). Кандидаты вокруг индекса вставки — единственные два, что могут быть ближайшими.
- ✗Соглашаться на проход O(n*m) по покупателю вместо бинарного поиска
- ✗Проверять лишь одного соседа точки вставки, упуская более близкую сторону
- ✗Спаривать отсортированные списки по индексам, игнорируя неограниченный запас
- →Почему нужно проверять обоих соседей индекса
bisect_left? - →Как слияние двумя указателями по двум отсортированным спискам даёт ту же оценку?
Оглавление
Задача
Реализуйте total_dissatisfaction: для каждого покупателя возьмите ближайший товар и просуммируйте abs(need - chosen) за O(n log n).
Решение
from bisect import bisect_left
def total_dissatisfaction(goods, needs):
goods = sorted(goods)
total = 0
for need in needs:
i = bisect_left(goods, need)
best = float("inf")
if i < len(goods):
best = min(best, abs(goods[i] - need)) # сосед сверху
if i > 0:
best = min(best, abs(goods[i - 1] - need)) # сосед снизу
total += best
return totalКлючевые моменты
- Сортируем товары один раз;
bisect_leftдаёт точку вставки за O(log n). - Ближайший товар — это либо
goods[i], либоgoods[i-1]; проверяем обоих. - Перебор по всем товарам на покупателя был бы O(n*m).
Оглавление
