Решение задачи Боксёры с Codeforces
С пояснением   Просмотров: 62
Есть n боксёров, вес i-го равен ai. Каждый из них перед соревнованием может изменить свой вес не более чем на 1 (вес не может стать равным нулю, то есть должен остаться положительным). Вес — это всегда целое число.
Необходимо выбрать наибольшую по количеству человек такую команду боксёров, что все веса боксёров в ней — различны.
Напишите программу, которая для заданных текущих значений ai найдет максимальное возможное количество боксёров в команде.
Возможно, что после какого-то изменения вес какого-то боксера станет 150001 (но не больше).
Необходимо выбрать наибольшую по количеству человек такую команду боксёров, что все веса боксёров в ней — различны.
Напишите программу, которая для заданных текущих значений ai найдет максимальное возможное количество боксёров в команде.
Возможно, что после какого-то изменения вес какого-то боксера станет 150001 (но не больше).
Пояснение к задаче
Пусть lst равно последнему весу боксера, взятого в команду. Изначально lst=∞. Отсортируем всех боксеров в порядке невозрастания их весов и пройдем по всем боксерам слева направо. Если текущий боксер имеет вес w, то давайте попробуем взять его с весом w+1 (мы можем сделать это, если w+1