2 лайка
Правило 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.
Теперь нужно просто решить обычную задачу о дедлайнах.
5 лайков