Разбор добавил Александр Чистяков
В первую очередь отсортируем всех игроков по неубыванию ПП.
Очевидно, что если в сформированную команду входят игроки с номерами (полученными при сортировке) 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 чисел. Требуется выбрать подмножество с максимальной суммой так, чтобы максимальный элемент подмножества не превосходил суммы двух минимальных.
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.
Выходные данные
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.