Advertisement
LilChicha174

Untitled

Jan 14th, 2025
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.90 KB | None | 0 0
  1. #Мы имеем отсортированный список товаров, представленных целыми числами. Также у нас есть несколько покупателей, каждый из которых #имеет целочисленную потребность. Если покупатель хочет число x, а среди товаров есть именно x, то неудовлетворенность равна 0. Если #точного совпадения нет, то покупатель берет ближайший по значению товар, а неудовлетворенность равна модулю разницы между x и #купленным значением. Товары не ограничены в количестве, один товар можно «продать» нескольким покупателям. Необходимо вычислить #суммарную неудовлетворенность всех покупателей.
  2.  
  3. #Пример
  4.  
  5. #Пусть имеется список товаров goods [5, 3, 5, 5, 8, 3] и два покупателя с потребностями 5 и 6. После сортировки товаров получаем [3, 3, #5, 5, 5, 8]. Для покупателя с потребностью 5 находим точное совпадение, неудовлетворенность равна 0. Для покупателя с потребностью 6 #ближайший товар 5, неудовлетворенность 1. Суммарная неудовлетворенность равна 0 плюс 1, то есть 1.
  6.  
  7. #Идея оптимального решения
  8. #Для начала товары сортируются. Затем для каждого покупателя с потребностью need с помощью бинарного поиска определяется позиция #вставки этого числа в отсортированный список товаров. Далее проверяются, во сколько обходится покупка ближайшего элемента справа и ####(если есть) ближайшего элемента слева от позиции вставки, чтобы выбрать тот, который дает меньшую разницу. Сложность работы состоит #из сортировки списка товаров за n log n и выполнения m бинарных поисков за m log n, где n это размер списка товаров, а m это #количество покупателей. Суммарно получается n log n плюс m log n.
  9.  
  10.  
  11. def binary_search_left(arr, target):
  12.     """
  13.    Возвращает индекс, куда можно вставить 'target' в массив 'arr',
  14.    чтобы сохранить сортировку (аналог bisect_left).
  15.    """
  16.     left, right = 0, len(arr)
  17.     while left < right:
  18.         mid = (left + right) // 2
  19.         if arr[mid] < target:
  20.             left = mid + 1
  21.         else:
  22.             right = mid
  23.     return left
  24.  
  25.  
  26. def total_dissatisfaction(goods, buyerNeeds):
  27.     """
  28.    Возвращает суммарную неудовлетворённость всех покупателей.
  29.    goods: список (list) целых чисел товаров (размер n)
  30.    buyerNeeds: список (list) целых чисел потребностей (размер m)
  31.    """
  32.     # 1. Сортируем товары (in-place)
  33.     goods.sort()
  34.    
  35.     # 2. Для каждого покупателя найдём ближайший товар с помощью бинарного поиска
  36.     total_diff = 0
  37.     n = len(goods)
  38.    
  39.     for need in buyerNeeds:
  40.         # Индекс для вставки (аналог bisect_left)
  41.         pos = binary_search_left(goods, need)
  42.        
  43.         # Собираем кандидатов (товар на позиции pos и pos-1, если валидны)
  44.         candidates = []
  45.         if pos < n:
  46.             candidates.append(goods[pos])
  47.         if pos - 1 >= 0:
  48.             candidates.append(goods[pos - 1])
  49.        
  50.         # Вычисляем минимальную разницу
  51.         diff = min(abs(need - c) for c in candidates)
  52.         total_diff += diff
  53.    
  54.     return total_diff
  55.  
  56.  
  57. # -------------------
  58. # Пример использования
  59. if __name__ == "__main__":
  60.     goods = [8, 3, 5]
  61.     buyerNeeds = [5, 6]
  62.     result = total_dissatisfaction(goods, buyerNeeds)
  63.     print("Суммарная неудовлетворённость:", result)
  64.     # Ожидаем:
  65.     # - для покупателя с need=5 -> товар 5 (разница = 0)
  66.     # - для покупателя с need=6 -> товар 5 (разница = 1)
  67.     # Итого: 1
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement