Задача №994. Сплоченная команда
Разбор добавил Александр Чистяков
В первую очередь отсортируем всех игроков по неубыванию ПП. Очевидно, что если в сформированную команду входят игроки с номерами (полученными при сортировке) i и j (i < j), то и любого игрока с номером k (i < k < j) тоже можно включить не нарушив сплочённость. То есть команда с максимальным ПП обязательно представляет собой непрерывное множество соседних по ПП игроков. Пускай l - указатель на игрока с самым маленьким ПП в нашей команде, а r - указатель на игрока самым высоким ПП. Очевидно, что команда из самого слабого и пред самого слабого игроков - сплочённая (случай для l = 0, r = 1 нас устраивает). Случай для 0 и 1 игроков можно рассмотреть отдельно. Объявим 2 переменные MaxRez и CurRez, в которых будем хранить наилучший из полученных суммарных ПП и ПП текущей команды соответственно. Пускай у нас набрана сплочённая команда максимальной численности с самым опытным игроком под номером r. Тогда, чтобы добавить в нашу команду игрока с номером r+1 достаточно, чтобы сумма ПП игроков с номерами l и l+1 была не меньше чем ПП r+1 игрока. Будем сдвигать левую границу, пока не достигнем такого равенства (очевидно, из предыдущей команды останется хотя бы 1 игрок, так как ПП[r]+ПП[r+1] < ПП[l+1] при r = l). При этом, при увеличении r мы будем увеличивать CurRez на ПП[r+1], а при увеличении l - уменьшать на ПП[l]. Если после добавления каждого из игроков обновлять значение MaxRez (MaxRez = max(MaxRez,CurRez)) то после одного прохода по массиву в переменной MaxRez будет храниться искомое значение. Чтобы по имеющемуся значению восстановить состав лучшей команды, достаточно ещё раз повторить описанные выше действия, но вместо обновления MaxRez смотреть: если значения CurRez и MaxRez совпали, то вывести численность команды (l-r+1), изначальные номера игроков от l до r, и прекратить работу программы. Отметим, что указатели l и r проходят по массиву не более одного раза, следовательно суммарная сложность алгоритма O(N*logN + N + N): сортировка и два прохода по массиву)
Дано N чисел. Требуется выбрать подмножество с максимальной суммой так, чтобы максимальный элемент подмножества не превосходил суммы двух минимальных.
Сдать: для сдачи задач необходимо войти в систему
97
statement