26. Прикладная задача: Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по…
Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы.
В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:
- все $2N$ чисел, обозначающих срок хранения и срок годности к употреблению для $N$ продуктов, упорядочивают по возрастанию;
- если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
- если минимальное число – это срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
- если число обозначает срок хранения или годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех $N$ продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более высокие места.
Это прямое моделирование описанного алгоритма. Собираем все $2N$ чисел, помечая каждое двумя вещами: номером продукта и типом — срок хранения или срок годности. Сортируем по возрастанию и идём по списку.
Для очередного числа смотрим, размещён ли уже его продукт. Если да, число пропускаем. Если нет, то при типе «срок хранения» продукт встаёт на первое свободное место с начала, а при типе «срок годности» — на первое свободное с конца. Достаточно держать два указателя: front растёт от единицы, back убывает от $N$.
Последний обработанный таким образом продукт и есть ответ на первый вопрос, а количество продуктов выше него равно его позиции минус один.
f = open('26-09.txt')
n = int(f.readline())
nums = []
for i in range(1, n+1):
a, b = map(int, f.readline().split())
nums.append((a, i, 'A')) # срок хранения
nums.append((b, i, 'B')) # срок годности
nums.sort()
placed = {}
front, back = 1, n
for _, i, t in nums:
if i in placed: # продукт уже размещён
continue
if t == 'A':
placed[i] = front
front += 1
else:
placed[i] = back
back -= 1
last, pos = i, placed[i]
print(last, pos - 1) # 9 464
Проверка. Продуктов $972$, все они размещаются. Последним встаёт продукт номер $9$ со сроками $95109$ и $96164$ — его срок хранения оказался самым большим среди всех неразмещённых чисел. Он занимает позицию $465$, значит выше него стоят $464$ продукта. Предыдущие два шага заняли позиции $467$ и $466$ с конца, так что середина рейтинга сомкнулась ровно на нём. На типовом примере из условия программа выдаёт $3$ и $3$.