Как найти универсальный язык с инопланетянами и не обанкротиться на конфетах 🍬👽
👋 Привет, земляне и потенциальные инопланетяне в моем блоге! Сегодня у нас не просто задачка, а целая галактическая драма. Представьте, что инопланетяне прибыли на Землю и объявили, что теперь весь мировой экономический порядок определяется... конфетами. Да-да, вы не ослышались, ребята. Сахарная промышленность взлетает до небес! 🚀🍬
Что нового я узнаю
- Как работать с массивами в Python на примере жизненно важной задачи.
- Как решить задачу о минимальном распределении ресурсов (конфет, в данном случае).
Подводные камни
- Осторожно, не упустите из виду требование, что у каждого ребёнка должно быть хотя бы одна конфета!
- Внимание на порядок детей и их рейтинги.
🍭 Итак, что за миссия у нас сегодня?
Нам дан массив ratings, где каждый элемент — это рейтинг ребёнка в этой сахарной вселенной. Наша задача — раздать конфеты так, чтобы у каждого ребёнка была хотя бы одна конфета и чтобы дети с большим рейтингом получали больше конфет, чем их соседи. Цель? Минимизировать количество потраченных конфет.
Полное условие задачи на ЛитКоде.
Итак, как бы вы решили эту задачу на своей новой рабочей станции, которая, кстати, теперь принадлежит инопланетянам? 🛸
Шаг 1: Подготовка к "Захвату Конфет" 🍬👽
Перед тем как мы начнем воображаемое "распределение конфет по рейтингу", давайте создадим массив для хранения количества конфет для каждого ребёнка. И пусть каждый ребёнок получит по одной конфете. Представьте это как стартовый пакет для каждого землянина в нашей новой сахарной экономике.
# Создаем массив для хранения конфет.
# По умолчанию каждый ребенок получает одну конфету
candies = [1] * len(ratings)
Шаг 2: Первый Проход - Следуем За Сахарным Трейлом 🍭👣
Теперь мы будем двигаться слева направо и проверять, не нужно ли дать ребенку с более высоким рейтингом больше конфет. Если рейтинг текущего ребенка выше, чем у предыдущего, мы увеличиваем количество его конфет на 1.
# Первый проход: слева направо
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
Шаг 3: Второй Проход - Возвращаемся Обратно 🔄🍬
Теперь, когда мы дошли до "конца Вселенной", пора вернуться обратно. Таким образом, мы убедимся, что у детей с более высоким рейтингом действительно больше конфет.
# Второй проход: справа налево
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
Финальный код решения: 🎉
А теперь, мои дорогие земляне и потенциальные инопланетные владыки, представляю вашему вниманию финальный код этой космической задачи!
class Solution:
def candy(self, ratings: List[int]) -> int:
# Стартовый пакет конфет для каждого ребенка
candies = [1] * len(ratings)
# Первый проход: слева направо. Все очень логично,
# как и в любой космической экспедиции.
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Второй проход: справа налево.
# Время назад не вернешь, но конфеты можно!
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
# Итоговое количество конфет,
# которое нужно для подкупа инопланетян.
return sum(candies)
Асимптотика 🤓
Что ж, говоря простым языком, асимптотика этого решения O(n), что означает, что оно масштабируется линейно с количеством детей. Во! Астрономия и математика в одном флаконе! 🌌🔢
Анекдот 🤣
Почему инопланетяне так любят алгоритмы сортировки?
Потому что они всегда пытаются найти наилучший способ "взять и улететь" из любой сложной ситуации на Земле! 🛸🌍