Сортировка как жадность

Если посмотреть на жадные решения, окажется, что почти все они устроены одинаково: отсортировать по некоторому ключу и пройтись по порядку. Вся сложность — в выборе ключа.

Угадывать его не нужно. Ключ выводится, и способ вывода один и тот же.

Обмен соседей

Рассуждение. Пусть оптимальный ответ — какой-то порядок элементов. Возьмём в нём двух соседей и спросим: при каком условии выгодно поставить их именно в таком порядке?

Ответ на этот вопрос и есть ключ сортировки. Логика: если для любой пары соседей известно, кто должен идти первым, то весь порядок задан однозначно — это и есть сортировка с таким компаратором.

Строгое обоснование: любой порядок превращается в отсортированный обменами соседей (это буквально пузырьковая сортировка), и ни один обмен не ухудшает ответ. Значит, отсортированный порядок не хуже оптимального.

Пример: минимум суммарного ожидания

Есть $n$ работ. Работа $i$ выполняется $t_i$ времени и имеет важность $w_i$. Работы делаются по очереди. Нужно минимизировать

$$\sum_i w_i \cdot (\text{момент завершения работы } i)$$

Применим обмен. Пусть в порядке рядом стоят работы $a$ и $b$, а до них прошло время $T$. Считаем вклад пары в обоих вариантах:

порядок	вклад
сначала $a$	$w_a(T + t_a) + w_b(T + t_a + t_b)$
сначала $b$	$w_b(T + t_b) + w_a(T + t_b + t_a)$

Вычтем одно из другого. Всё, что зависит от $T$, сокращается, остаётся сравнение $w_b t_a$ против $w_a t_b$. Значит, $a$ должно идти раньше, когда

$$\frac{t_a}{w_a} < \frac{t_b}{w_b}$$

sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
    return a.time * b.weight < b.time * a.weight;   // t_a/w_a < t_b/w_b
});

Проверено перебором всех перестановок: на двадцати тысячах случайных наборов до шести работ жадный порядок совпал с оптимальным во всех.

Обратите внимание, что сокращение $T$ — не случайность, а суть метода. Именно поэтому достаточно смотреть на пару: остальная часть порядка на сравнение не влияет.

И снова сравнение через умножение вместо деления — иначе вылезут ошибки округления там, где их не ждёшь.

Каталог ключей

Что получается обменом в типовых задачах:

задача	ключ
максимум непересекающихся отрезков	правый конец, возрастая
минимум ожидания (равные веса)	длительность, возрастая
минимум взвешенного ожидания	$t_i / w_i$, возрастая
непрерывный рюкзак	$c_i / m_i$, убывая
дедлайны со штрафом	дедлайн, возрастая
склеить числа в максимальное	$a + b > b + a$ как строки
пары «сильный с сильным»	оба массива в одном порядке
пары «сильный со слабым»	один по возрастанию, другой по убыванию

Предпоследние две строки — частный случай неравенства о перестановках: сумма произведений $\sum a_i b_{\sigma(i)}$ максимальна, когда оба набора отсортированы одинаково, и минимальна, когда противоположно.

Строка про склейку заслуживает пояснения: чтобы из чисел $\{9, 91, 918\}$ собрать максимальное число, сортировать по значению или по длине нельзя. Правильный компаратор — сравнить конкатенации: $a$ идёт раньше $b$, если строка $a + b$ больше строки $b + a$. Это тоже вывод обменом, просто вклад пары считается конкатенацией.

Пример посложнее: игра с добавкой

Алиса и Боб по очереди забирают числа из набора, Алиса ходит первой. Алиса максимизирует разность своей суммы и суммы Боба, Боб минимизирует. Перед игрой Боб может суммарно добавить к числам не больше $k$ (по целому, только увеличивая).

Сначала игра без добавки. Обе стороны действуют одинаково: берут наибольшее оставшееся. Значит, после сортировки по убыванию Алисе достаются элементы с чётными индексами, Бобу — с нечётными, и разность равна знакопеременной сумме.

Теперь добавка. Боб хочет уменьшить разность, то есть подтянуть свои элементы к соседним слева. Поднимать выше соседа бессмысленно: тогда Алиса просто заберёт этот элемент, и выигрыш пропадёт.

sort(a.rbegin(), a.rend());
for (size_t i = 1; i < a.size(); i += 2) {
    long long add = min<long long>(k, a[i - 1] - a[i]);
    a[i] += add;
    k -= add;
}

Проверено полным перебором: на четырёхстах случайных наборах до четырёх чисел с бюджетом до четырёх эта раздача совпала с оптимальной, найденной перебором всех распределений $k$ и минимаксом по дереву игры.

Если бюджета хватает на всё, каждая пара выравнивается, и разность становится нулевой — это предельный случай, по которому удобно проверять код.

Когда обмен не срабатывает

Метод даёт ключ не всегда. Признак: разность вкладов не сокращается — в ней остаётся $T$ или элементы, стоящие не рядом.

Это означает, что порядок соседей зависит от всего остального, и одной сортировкой задача не решается. Обычно дальше идёт динамика.

Второй признак — когда обмен даёт несогласованный порядок: $a$ раньше $b$, $b$ раньше $c$, но $c$ раньше $a$. Такой компаратор не задаёт порядка, и sort с ним не просто ошибётся, а упадёт. Если ваш ключ такое допускает — жадность неверна, и это хорошо, что выяснилось до отправки.