Сложность: medium
Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня.
Пример:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
👨💻 Алгоритм:
1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.
2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.
3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.
😎 Решение:
def maxSatisfied(customers, grumpy, minutes):
total_satisfied = 0
additional_satisfied = 0
max_additional_satisfied = 0
for i in range(len(customers)):
if grumpy[i] == 0:
total_satisfied += customers[i]
else:
additional_satisfied += customers[i]
if i >= minutes:
if grumpy[i - minutes] == 1:
additional_satisfied -= customers[i - minutes]
max_additional_satisfied = max(max_additional_satisfied, additional_satisfied)
return total_satisfied + max_additional_satisfied
Ставь 👍 и забирай 📚 Базу знаний