Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #Мы имеем отсортированный список товаров, представленных целыми числами. Также у нас есть несколько покупателей, каждый из которых #имеет целочисленную потребность. Если покупатель хочет число x, а среди товаров есть именно x, то неудовлетворенность равна 0. Если #точного совпадения нет, то покупатель берет ближайший по значению товар, а неудовлетворенность равна модулю разницы между x и #купленным значением. Товары не ограничены в количестве, один товар можно «продать» нескольким покупателям. Необходимо вычислить #суммарную неудовлетворенность всех покупателей.
- #Пример
- #Пусть имеется список товаров goods [5, 3, 5, 5, 8, 3] и два покупателя с потребностями 5 и 6. После сортировки товаров получаем [3, 3, #5, 5, 5, 8]. Для покупателя с потребностью 5 находим точное совпадение, неудовлетворенность равна 0. Для покупателя с потребностью 6 #ближайший товар 5, неудовлетворенность 1. Суммарная неудовлетворенность равна 0 плюс 1, то есть 1.
- #Идея оптимального решения
- #Для начала товары сортируются. Затем для каждого покупателя с потребностью need с помощью бинарного поиска определяется позиция #вставки этого числа в отсортированный список товаров. Далее проверяются, во сколько обходится покупка ближайшего элемента справа и ####(если есть) ближайшего элемента слева от позиции вставки, чтобы выбрать тот, который дает меньшую разницу. Сложность работы состоит #из сортировки списка товаров за n log n и выполнения m бинарных поисков за m log n, где n это размер списка товаров, а m это #количество покупателей. Суммарно получается n log n плюс m log n.
- def binary_search_left(arr, target):
- """
- Возвращает индекс, куда можно вставить 'target' в массив 'arr',
- чтобы сохранить сортировку (аналог bisect_left).
- """
- left, right = 0, len(arr)
- while left < right:
- mid = (left + right) // 2
- if arr[mid] < target:
- left = mid + 1
- else:
- right = mid
- return left
- def total_dissatisfaction(goods, buyerNeeds):
- """
- Возвращает суммарную неудовлетворённость всех покупателей.
- goods: список (list) целых чисел товаров (размер n)
- buyerNeeds: список (list) целых чисел потребностей (размер m)
- """
- # 1. Сортируем товары (in-place)
- goods.sort()
- # 2. Для каждого покупателя найдём ближайший товар с помощью бинарного поиска
- total_diff = 0
- n = len(goods)
- for need in buyerNeeds:
- # Индекс для вставки (аналог bisect_left)
- pos = binary_search_left(goods, need)
- # Собираем кандидатов (товар на позиции pos и pos-1, если валидны)
- candidates = []
- if pos < n:
- candidates.append(goods[pos])
- if pos - 1 >= 0:
- candidates.append(goods[pos - 1])
- # Вычисляем минимальную разницу
- diff = min(abs(need - c) for c in candidates)
- total_diff += diff
- return total_diff
- # -------------------
- # Пример использования
- if __name__ == "__main__":
- goods = [8, 3, 5]
- buyerNeeds = [5, 6]
- result = total_dissatisfaction(goods, buyerNeeds)
- print("Суммарная неудовлетворённость:", result)
- # Ожидаем:
- # - для покупателя с need=5 -> товар 5 (разница = 0)
- # - для покупателя с need=6 -> товар 5 (разница = 1)
- # Итого: 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement