Жадность на строках и числах

Отдельный класс жадных задач: из строки или числа надо что-то удалить или переставить, чтобы результат стал минимальным или максимальным лексикографически.

Жадность здесь почти всегда верна, но реализуется не так, как подсказывает первая мысль.

Удалить k цифр, получив минимум

Дано число строкой. Удалить ровно $k$ цифр, чтобы оставшееся число было минимальным.

Наивная идея — $k$ раз найти и удалить наибольшую цифру. Неверно: важна не величина цифры, а её позиция. В числе 1924 при $k = 1$ удалять надо девятку, а в 4219 — четвёрку, хотя девятка больше.

Правильный критерий: цифру стоит удалить, если следующая за ней меньше. Тогда число уменьшится в старшем разряде, а это важнее всего остального.

Реализуется стеком за один проход:

string removeDigits(const string& s, int k) {
    string result;
    for (char c : s) {
        while (k > 0 && !result.empty() && result.back() > c) {
            result.pop_back();
            k--;
        }
        result += c;
    }
    while (k-- > 0 && !result.empty()) result.pop_back();   // остаток срезаем с конца
    return result;
}

Два места, которые легко пропустить.

Хвостовое удаление. Если строка неубывающая (1234), внутренний while не сработает ни разу, и $k$ останется неизрасходованным. Тогда удалять надо с конца — там самые младшие разряды.

Ведущие нули. После удаления результат может начинаться с нулей. По условию обычно требуется убрать их (и отдельно обработать случай, когда осталось 0).

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

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

Тот же приём для максимума

Максимальная подпоследовательность длины $n - k$ получается заменой одного знака:

while (k > 0 && !result.empty() && result.back() < c) { result.pop_back(); k--; }

Тоже проверено перебором — совпадает.

Эта конструкция называется монотонным стеком: в стеке поддерживается неубывающая (или невозрастающая) последовательность. Она же лежит в основе задач «ближайший больший справа» и «максимальный прямоугольник в гистограмме».

Склеить числа в максимальное

Даны числа. Приписать их друг к другу в таком порядке, чтобы получилось максимальное число.

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

sort(v.begin(), v.end(), [](const string& a, const string& b) {
    return a + b > b + a;
});

Это классический вывод обменом соседей: вклад пары в результат — это ровно её конкатенация, всё остальное не меняется.

Компаратор корректен: он задаёт строгий порядок, потому что конкатенация ассоциативна, и транзитивность не нарушается. Отдельно обработайте случай, когда все числа нулевые, — иначе получите 000 вместо 0.

Лексикографически минимальная перестановка

Задача вида «сделайте строку минимальной, разрешено $k$ обменов соседних символов» решается тем же способом: идём слева направо, для каждой позиции ищем минимальный символ в пределах досягаемости и перетаскиваем его сюда, тратя обмены.

for (int i = 0; i < n && k > 0; i++) {
    int best = i;
    for (int j = i + 1; j < n && j - i <= k; j++)
        if (s[j] < s[best]) best = j;
    k -= best - i;
    for (int j = best; j > i; j--) swap(s[j], s[j - 1]);
}

Жадность верна, потому что старший разряд важнее всех последующих вместе взятых: любой выигрыш в позиции $i$ перевешивает любой проигрыш дальше.

Это же соображение — общее для всего класса задач. Лексикографический порядок делает жадность корректной автоматически: улучшение в самой левой позиции нельзя перебить ничем справа. Поэтому там, где обычная жадность требует доказательства, лексикографическая почти всегда верна.

Где всё-таки ломается

Осторожность нужна, когда лексикографический порядок сравнивает строки разной длины. Тогда «взять меньший символ сейчас» может укоротить результат, а короткая строка не обязана быть меньше длинной.

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