Question

B. Цена за мороженное ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт вводстандартный ввод выводстандартный вывод Вы продаете мороженное. Себестоимость одного мороженного k тенге. Это значит, что если вы продаете одно мороженное по x тенге, тогда прибыль с одного мороженного будет x−k тенге. Есть n клиентов, для каждого клиента i известно максимальная сумма денег si тенге, которую он готов потратить на мороженное. Каждый клиент купить столько мороженного, сколько сможет купить. Выберите цену мороженного таким образом, чтобы максимизировать суммарную прибыль. Входные данные В первой строке находятся два целых числа n,k (1≤n≤2⋅105 , 0≤k≤106 ) — количество клиентов и себестоимость одного мороженного. Во второй строке находятся n целых числа s1,s2,⋯,sn (1≤si≤106 ). Выходные данные Выведите максимальную возможную прибыль. В первом примере одно мороженное выгодно продавать по 7 тенге. Тогда четвертый клиент купить 2 мороженное, а остальные 4 по одному. Всего продадим 6 мороженных. Прибыль с одного мороженного 5 (7−2 ) тенге, тогда суммарная прибыль 6⋅5=30 тенге.

Answer 1

Ответ:Вот код на пайтон

Объяснение:

k = int(input("Введите себестоимость одного мороженного: "))

n = int(input("Введите количество клиентов: "))

max_profit = 0

price = 0

for i in range(n):

   s = int(input("Введите максимальную сумму денег, которую готов потратить клиент {}: ".format(i+1)))

   profit = min(s, k+i) - k

   if profit > max_profit:

       max_profit = profit

       price = k + i

print("Цена мороженного: {} тенге".format(price))

Answer 2

Для решения этой задачи можно использовать жадный алгоритм. Мы хотим максимизировать суммарную прибыль, поэтому будем продавать мороженое тем клиентам, у которых наибольшая сумма денег.

1. Считываем количество клиентов n и себестоимость мороженого k.
2. Считываем список максимальных сумм денег si для каждого клиента.
3. Сортируем список сумм денег в порядке убывания.
4. Для каждой суммы денег si в отсортированном списке:
   • Проверяем, сколько мороженого можно продать по текущей цене (si - k).
   • Если полученное количество мороженого больше нуля, добавляем его к общему количеству проданных мороженых.
   • Увеличиваем общую прибыль на прибыль с одного мороженного, умноженную на количество проданных мороженых.
5. Выводим общую прибыль.

Ниже представлена реализация данного алгоритма на языке Python:

pythonCopy code
n, k = map(int, input().split())
s = list(map(int, input().split()))

s.sort(reverse=True)  # Сортируем список сумм денег в порядке убывания

total_profit = 0
sold_ice_creams = 0

for si in s:
    num_ice_creams = si - k  # Сколько мороженого можно продать по текущей цене
    
    if num_ice_creams > 0:
        total_profit += num_ice_creams  # Увеличиваем общую прибыль
        sold_ice_creams += num_ice_creams  # Увеличиваем количество проданных мороженых

profit_per_ice_cream = s[0] - k  # Прибыль с одного мороженного
total_profit += profit_per_ice_cream * sold_ice_creams  # Увеличиваем общую прибыль на прибыль с одного мороженного, умноженную на количество проданных мороженых

print(total_profit)

Этот алгоритм имеет сложность O(n log n) из-за сортировки списка сумм денег.