Сколько пицц могут оставаться горячими в любой момент времени?


Могу только скринами, группа закрыта

2 симпатии

Еще сэмплы:

1 симпатия

Правило 15 символов включил я.

Так заголовки гораздо информативнее и помогают с поиском темы если у кого-то возникнет подобный вопрос.

А ну ладно тогда

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

Как проверять это за O(N)

Они уже распределены в правильном порядке и нам нужно проверить что мы можем взять всех.

a_1 + a_2 + a_3 + ... + a_n \leq min(a_1 + b_1, a_1 + a_2 + b_2, a_1 + a_2 + a_3 + b_3, ..., a + 1 + ... + a_n + b_n)
Раскроем :
a_1 + a_2 + a_3 + ... + a_n \leq a_1 + b_1
a_1 + a_2 + a_3 + ... + a_n \leq a_1 + a_2+ b_2
a_1 + a_2 + a_3 + ... + a_n \leq a_1 + a_2 + a_3 + b_3

a_1 + a_2 + a_3 + ... + a_n \leq a_1 + a_2 + a_3 + ... + a_n + b_n

Уберём равные с двух сторон :

a_2 + a_3 + ... + a_n \leq b_1
a_3 + ... + a_n \leq b_2

a_n \leq b_{n - 1}

Теперь давай для удобства перевернём всё и выйдет:

a_1 \leq b_2
a_1 + a_2 \leq b_3
a_1 + a_2 + a_3 \leq b_4

a_1 + a_2 + a_3 + ... + a_{n - 1} \leq b_n

Перед тем как идти дальше посмотрите что под спойлером.

Перед тем как решать задачу подумаем о популярной задаче о дедлайнах. Нам дано два массива t и d, мы выполняем работу i за t_i и мы должны её закончить до d_i. Нам нужно максимизировать кол-во выполненных работ. Если мы выбрали работы i_1, i_2, i_3, i_4, ..., то тогда можно будет переставить их так чтобы выполнялось d_{i_1} \leq d_{i_2} \leq d_{i_3} \leq ...

Док-во

Пусть существует пара соседних d_{i_j} > d_{i_{j + 1}}, тогда мы можем поменять их местами не нарушив дедлайны. Заметим что обмен {i_j} и i_{j + 1} повлияет только на эти элементы, другие не будут затронуты этим, теперь распишем изменения.
sum = t_{i_1} + t_{i_2} + ... + t_{i_{j - 1}}

До : sum + t_{i_j} \leq d_{i_j} и sum + t_{i_j} + t_{i_{j+1}} \leq d_{i_{j + 1}}.
После: sum + t_{i_{j + 1}} \leq d_{i_{j + 1}} и sum + t_{i_j} + t_{i_{j + 1}} \leq d_{i_j}
Давайте заметим что условия после будут истинны так как выполняется d_{i_j} > d_{i_{j + 1}}, а значит дедлайны не были нарушены.

Теперь следуя алгоритму из темы Как доказать правильность этого алгоритма?. Мы можем выполнить максимальное количество работ. Если у меня будет время я сам распишу док-во там.

Эта задача является популярной задачей на жадные алгоритмы, она называется “Задача о дедлайнах”.

Теперь осталось свести нашу задачу к этой.

Сводим и решаем её

a_1 \leq b_2
a_1 + a_2 \leq b_3
a_1 + a_2 + a_3 \leq b_4

a_1 + a_2 + a_3 + ... + a_{n - 1} \leq b_n

Прибавим a_i в обе стороны

a_1 + a_2 \leq b_2 + a_2
a_1 + a_2 + a_3 \leq b_3 + a_3
a_1 + a_2 + a_3 + a_4 \leq b_4 + a_4

a_1 + a_2 + a_3 + ... + a_{n - 1} + a_n \leq b_n + a_n

Давайте заметим что это один в один задача о дедлайнах, d_i = a_i + b_i t_i = a_i.

Теперь нужно просто решить обычную задачу о дедлайнах.

4 симпатии