Стратегия победы: жадные — когда жадность ломается и как её спасти СТРАТЕГИЯ

О чём эта статья

Серия «Стратегия победы» — про траекторию тренировки. Берём одну технику и проходим её на трёх уровнях нарастающей сложности, явно фиксируя, что именно усложняется между ступенями. Тема этой статьи — жадные алгоритмы, и центральный сюжет — не «как написать жадный», а когда он ломается и какими способами его «лечат».

Жадные легко производят иллюзию, что задача решена: первое попавшееся правило работает на маленьких тестах. Реальные ошибки приходят там, где задача вроде бы «жадная по структуре», но: либо ключ сортировки нужен нестандартный (ступень 1); либо локальный выбор влияет на следующий шаг и нужно «переносить остаток» (ступень 2); либо локального правила вообще нет, и единственный способ — DP, в котором жадная интуиция остаётся в порядке обхода (ступень 3).

---

Ядро техники

Жадный = на каждом шаге выбираем «локально лучшее» и не откатываемся. Корректность обосновывается через exchange argument: любое отличающееся оптимальное решение можно цепочкой обменов превратить в жадное, не ухудшив. Если такая цепочка не строится — жадный неверен.

Соседняя статья этой серии («Алгоритмические основы #4 — Жадные и exchange argument») разобрала шаблон рассуждения; здесь мы смотрим на расширение шаблона: что именно меняется в задачах, где «чисто жадный» уже не проходит.

Базовый шаблон (псевдокод)

отсортировать элементы по нужному ключу
для каждого элемента в этом порядке:
    принять или отвергнуть, обновить состояние
вернуть ответ

Сложность базового шаблона: $O(n \log n)$ — доминирует сортировка.

Что мы будем усложнять по мере роста:

• Ступень 1 → ступень 2: к локальному выбору добавляется «хвост», который надо переносить в следующий шаг (текущее решение влияет на ограничение для будущего).
• Ступень 2 → ступень 3: «локального правила» больше нет — есть структура, в которой выгодный выбор зависит от всей конфигурации впереди. Жадный заменяется DP с тем же порядком обхода.

---

Ступень 1 — CF ~1200 (чистый exchange argument)

Условие

Дано $n$ заданий. Задание $i$ занимает $t_i$ единиц времени. На одном процессоре выполняем задания по очереди. Время завершения $i$-го задания равно сумме длительностей всех заданий, поставленных не позже $i$-го. Найти минимальную сумму времён завершения по всем порядкам выполнения.

Ограничения. $1 \le n \le 10^5$, $1 \le t_i \le 10^9$.

Как применяется базовый шаблон

Заметим: если задание $j$ стоит на позиции $p_j$, то его длительность $t_j$ войдёт в сумму времён завершения $n - p_j + 1$ раз — оно учитывается в собственном «завершении» и в завершении каждого следующего. Чтобы минимизировать сумму, длинные задания должны иметь наименьший коэффициент, то есть стоять в конце.

Жадный: отсортировать задания по возрастанию $t_i$. Запустить в этом порядке.

Exchange argument

Предположим, в оптимальном порядке есть пара соседних заданий $j$ (раньше) и $k$ (позже) с $t_j > t_k$. Поменяем их местами. На длительности других заданий это не влияет (они идут до или после обеих позиций). Влияет только на сумму завершений $j$ и $k$:

• Было: $t_j + (t_j + t_k) = 2 t_j + t_k$.
• Стало: $t_k + (t_k + t_j) = 2 t_k + t_j$.

Разница: было больше на $t_j - t_k > 0$. То есть обмен улучшил ответ. Любая «инверсия» в оптимуме приводит к противоречию. Значит, оптимум — это отсортированный порядок. ∎

Разбор на примере

$n = 3$, $t = [3, 1, 2]$. Сортируем: $[1, 2, 3]$. Времена завершения: $1, 1 + 2 = 3, 3 + 3 = 6$. Сумма: $10$.

Проверим другие порядки:

• $[3, 1, 2]$: $3, 4, 6$, сумма $13$.
• $[2, 1, 3]$: $2, 3, 6$, сумма $11$.

Жадный даёт минимум.

Код решения

Сложность: $O(n \log n)$.

Что закрыли

На этом уровне жадный — это «отсортировать по правильному ключу и один раз пройти». Состояние — буквально одна переменная cur (накопленная длительность). Exchange argument — двухсимвольная замена соседей.

Следующий шаг — жадный, где локальный выбор создаёт ограничение для следующего шага. Простое правило сохранится, но потребуется честно нести «хвост».

---

Ступень 2 — CF ~1500 (жадный с переносом «остатка»)

Условие

На прямой стоят $n$ заправок с координатами $x_1 < x_2 < \cdots < x_n$ и стоимостями литра топлива $c_1, \ldots, c_n$. Машина движется слева направо от заправки 1 до заправки $n$, расход — 1 литр на единицу расстояния. На каждой заправке можно купить любое количество литров. Объём бака — $V$ литров. Начальный объём — 0. Найти минимальную стоимость доезда до заправки $n$.

Ограничения. $1 \le n \le 10^5$, $1 \le V \le 10^9$, $1 \le x_i \le 10^9$, $1 \le c_i \le 10^9$. Гарантируется, что для каждого $i$ расстояние $x_{i + 1} - x_i \le V$.

Условие, чем эта задача сложнее ступени 1

В ступени 1 решение полностью определялось одним глобальным порядком. Здесь каждый локальный выбор (сколько литров купить на заправке $i$) влияет на доступные варианты в будущем: купили слишком много — потратили деньги по высокой цене; купили слишком мало — пришлось заправляться по ещё более высокой. Локального правила «отсортировать и пройти» нет.

Что меняется в шаблоне

• Состояние: теперь это не одна переменная, а остаток бака на каждой заправке плюс уже потраченные деньги.
• Решающее правило: на заправке $i$ заглядываем вперёд — есть ли впереди заправка с более дешёвым топливом, до которой хватит остатка?
  • Если есть — покупаем ровно столько, чтобы доехать до неё.
  • Если нет — заполняем бак до полного и едем дальше; в следующем дешёвом месте остаток ещё пригодится.

Это уже не «отсортировать», а жадный с просмотром вперёд и переносом неиспользованного остатка.

• Доказательство: exchange argument на парах заправок. Если в оптимуме мы купили на заправке $i$ больше, чем нужно до ближайшей более дешёвой $j$, можно сдвинуть «лишний» литр с $i$ на $j$ — стоимость уменьшится (литр стоит дешевле в $j$). Если в оптимуме мы купили меньше — значит, в какой-то более дорогой заправке между $i$ и $j$ мы заправились, что хуже. Цепочкой обменов приходим к жадному правилу.

Разбор на примере

$n = 5$, $V = 10$, $x = [0, 4, 9, 12, 15]$, $c = [3, 5, 1, 4, 2]$.

• Заправка 0 (цена 3). Ближайшая более дешёвая впереди — заправка 2 (цена 1), расстояние $9 - 0 = 9 \le 10$. Покупаем 9 литров. Стоимость: $27$. Остаток на заправке 2: 0.
• Заправка 2 (цена 1). Ближайшая более дешёвая впереди — заправка 4 (цена 2). Подождите, 4 не дешевле 1. Значит, дешёвых впереди нет. Заполняем бак до $V = 10$. Стоимость: $+10 = 37$. Остаток после заезда: 10.
• Заправка 3 (цена 4). Расход с заправки 2: $12 - 9 = 3$, остаток $10 - 3 = 7$.
  • Уже едем с бензином, ничего не покупаем. Ждём заправку 4.
• Заправка 4 (цена 2). Доехали с остатком $7 - (15 - 12) = 4 > 0$, до неё доехали бесплатно. Это конец маршрута: стоимость остаётся $37$.

Финальный ответ: 37.

Код решения

Для каждой заправки определим следующую более дешёвую за $O(n)$ через монотонный стек (классический шаблон «next smaller»):

Сложность: $O(n)$ на построение next_cheaper (каждая заправка попадает в стек и уходит из него по разу), $O(n)$ на основной проход. Итого $O(n)$.

Что закрыли

Ступень 2 — умение держать остаток между шагами и принимать решение, исходя из «не только сейчас, но и ближайшего будущего». Состояние выросло до пары (fuel, cost), появилось предвычисление вспомогательной структуры (next_cheaper). Это всё ещё жадный — но «жадный с памятью».

Следующий шаг — задачи, где локальное правило вообще не складывается, и нужен переход к DP. Жадная интуиция остаётся, но в виде порядка обработки.

---

Ступень 3 — CF ~1900 (жадный сломался, спасает DP)

Условие

Дано $n$ работ. Работа $i$ задана тройкой $(s_i, d_i, p_i)$: $s_i$ — момент, когда её можно начать (не раньше); $d_i$ — длительность (целое); $p_i$ — премия за выполнение. Работа считается выполненной, если её непрерывно делали с момента $s_i' \ge s_i$ до момента $s_i' + d_i$. Все работы — на одном процессоре, параллельно выполнять нельзя. Максимизировать суммарную премию.

Ограничения. $1 \le n \le 5000$, $1 \le s_i, d_i \le 10^9$, $1 \le p_i \le 10^9$.

Условие, чем эта задача сложнее ступени 2

Естественные жадные гипотезы все ломаются:

• «Сортировать по премии $p_i$ убыванию, брать жадно совместимые» — контрпример: одна жирная работа на длинный интервал блокирует две меньшие с большей суммарной премией.
• «Сортировать по окончанию $s_i + d_i$ возрастанию, брать совместимые» — это даст максимум числа работ, а не максимум премии.
• «Сортировать по $p_i / d_i$» (эффективности) — тоже строится контрпример.

Локальное правило для взвешенной непересекающейся выборки не существует. Стандартное решение — DP с порядком обхода по концу работ (это и есть жадная интуиция: «принимать решение в момент окончания работы»).

Что меняется в шаблоне

• Состояние: $f(i)$ — максимальная суммарная премия среди работ, которые закончились не позже конца $i$-й работы (в порядке возрастания конца). Перебор: либо $i$-ю работу не берём ($f(i) = f(i - 1)$), либо берём ($f(i) = f(j) + p_i$, где $j$ — последняя работа, заканчивающаяся не позже $s_i$).
• Переход: $f(i) = \max(f(i - 1), f(j) + p_i)$, где $j =$ найти бинпоиском по списку концов.
• Доказательство: стандартное по принципу оптимальности — каждая работа либо в оптимальном наборе, либо нет, и обе ветки рассматриваются.

Жадный порядок («по концу работ») сохраняется как порядок обхода DP — это и есть момент, в который жадная интуиция переходит в DP.

Разбор на примере

$n = 4$, работы (после нормализации к интервалам $[s, s + d]$):

Отсортируем по концу: уже в порядке 1, 2, 3, 4 концы 3, 5, 6, 8.

• $f(0) = 0$ (пустой набор).
• $f(1)$: работа 1, $s_1 = 0$, предыдущая совместимая — $j_1 = 0$ (нет). $f(1) = \max(0, 0 + 5) = 5$.
• $f(2)$: работа 2, $s_2 = 2$, ищем работы с концом $\le 2$ — нет, $j_2 = 0$. $f(2) = \max(5, 0 + 6) = 6$.
• $f(3)$: работа 3, $s_3 = 4$, ищем с концом $\le 4$ — работа 1 (конец 3). $j_3 = 1$. $f(3) = \max(6, f(1) + 4) = \max(6, 9) = 9$.
• $f(4)$: работа 4, $s_4 = 5$, ищем с концом $\le 5$ — работы 1 и 2. $j_4 = 2$. $f(4) = \max(9, f(2) + 7) = \max(9, 13) = 13$.

Ответ: 13 (работы 2 и 4).

Код решения

Сложность: $O(n \log n)$ — сортировка плюс бинпоиск на каждом шаге DP.

Что закрыли

Ступень 3 — точка, где жадный перестаёт быть алгоритмом, но остаётся интуицией. Состояние DP — массив $f[i]$, переход выбирает между «взять $i$-ю работу» и «пропустить». Главное умение этого уровня — увидеть, что естественного «локального правила» нет, и не пытаться его натянуть.

Дальнейший шаг — задачи, где даже такой DP не помещается по памяти / времени и нужны сжатия состояния (свёртки по последнему интересному параметру). Это уже за рамкой этой стратегии.

---

Карта траектории

---

Типичные ловушки на каждой ступени

• Ступень 1: неверный ключ сортировки. Кажется естественным «отсортировать по убыванию» вместо возрастания, или по другому параметру. Лекарство — построить exchange argument до написания кода и убедиться, что обмен инверсий улучшает ответ.
• Ступень 2: «оставить полный бак на потом» вместо честного просмотра вперёд. Жадный без структуры next_cheaper («заправляться по полной всегда») даёт WA на тестах, где впереди есть дешёвая заправка, до которой хватит. Лекарство — два правила в одном: «если есть дешёвая впереди — до неё, иначе — полный бак».
• Ступень 3: пытаться спасти жадный «эвристически». «Сортировка по премии $/$ длительности», «двухпроходные жадные», «жадный с откатом» — всё это даёт WA на тщательно подобранных тестах. Симптом: «работает на ручных примерах, падает на больших». Лекарство — переключиться на DP в момент, когда не получается доказать exchange argument.

---

План тренировки

1. Решить задачу ступени 1 самостоятельно. Цель — отработать exchange argument как метод доказательства.
2. На Codeforces в полосе ~1200 решить 3–5 задач с тегом greedy (фильтр по difficulty). Перепроверять каждое решение через «а доказал ли я обмен?».
3. Перейти к ступени 2. Если буксует более 30 минут — вернуться к шаблону next_cheaper (монотонный стек) — это часть базы, без неё ступень 2 не решается.
4. На Codeforces в полосе ~1500 — 3–5 задач с тегами greedy + two pointers или greedy + stack.
5. Ступень 3 — если жадная гипотеза не складывается за 15 минут, переключиться на DP. Главное умение — диагностировать «жадный не работает».
6. На Codeforces в полосе ~1700–1900 — 3–5 задач из набора «weighted interval scheduling» и его вариантов.

---

Итого

• Тема: жадные с расширением «локальное правило → перенос остатка → DP с жадным порядком».
• Траектория: CF ~1200 → ~1500 → ~1900, с усложнением состояния: одна переменная → пара с предвычислением → массив DP.
• Ключевое умение: диагностировать, когда жадный сломался, и переходить к нужной технике без попыток «заэвристить».