|
Название задачи: Сплочённая команда. |
 |
Условие
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных ее участников, но и сплоченность команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплоченной, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодежной сборной Москвы была поставлена задача сформировать сплоченную сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.
Формат входных данных
В первой строке входного файла e.in записано целое число N (0 £ N £ 30000). В последующих N строках записано по одному целому числу Pi (0 £ Pi £ 60000), представляющему собой ПП соответствующего игрока.
Формат выходных данных
В первой строке выходного файла e.out через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке - по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.
Примеры
|
e.in |
e.out |
|
4 1 5 3 3 |
3 11 2 3 4 |
|
5 100 20 20 20 20 |
2 120 1 2 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программаОтсортируем игроков в порядке возрастания их ПП с помощью любого эффективного алгоритма сортировки с вычислительной сложностью O(NlogN). При этом исходные номера игроков необходимо запомнить в отдельном массиве для последующего вывода ответа.
Критерием сплоченности команды является то, что ПП самого сильного игрока не превосходит суммы ПП двух самых слабых. Команду с максимальной суммой ПП всегда можно выбрать так, что игроки, в нее входящие, образуют непрерывную последовательность в отсортированном массиве.
Действительно, пусть существует игрок, не вошедший в команду, номер которого в отсортированном массиве больше номера самого слабого игрока команды, но меньше номера самого сильного. Тогда можно взять его в команду вместо самого слабого игрока. При этом команда, очевидно, останется сплоченной, а сумма ПП команды заведомо не уменьшится. Если по-прежнему существует игрок, не вошедший в команду, номер которого в отсортированном массиве больше номера самого слабого игрока команды, но меньше номера самого сильного, то можно повторно применить то же рассуждение. Эта процедура продолжается до тех пор, пока команда не составит непрерывную последовательность игроков в отсортированном массиве. Такой момент наступит, поскольку количество игроков между самым слабым и самым сильным игроками команды в отсортированном массиве на каждом шаге уменьшается, а количество игроков команды остается неизменным.
Таким образом, в отсортированном массиве необходимо найти непрерывную последовательность игроков, образующих сплоченную команду с максимальной суммой ПП. Кроме того необходимо аккуратно разбирать случай N = 0, а также учитывать то, что любая команда из одного или двух игроков является сплоченной. При других значениях N искомую последовательность игроков можно найти одним из двух способов.
1) Храним два указателя: на самого слабого и самого сильного игроков команды - i и j. В переменной sum храним сумму ПП игроков с i-го по j-й. Изначально i = 1, j = 2.
Пока j не превосходит N, делаем следующую операцию. Если ПП j-го игрока не превосходит суммы ПП i-го и (i+1)-го игроков (т.е. команда, состоящая из игроков с i-го по j-й, является сплоченной), то увеличиваем j на 1. Если при этом sum > res, где res - сумма ПП лучшей из уже найденных команд, то обновляем результат. Если же ПП j-го игрока указанную сумму превосходит, то увеличиваем i на 1. В зависимости от сдвига указателей нужно пересчитывать переменную sum.
Время работы алгоритма без учета сортировки - O(N), поскольку каждый указатель пробегает по массиву лишь однажды.
2) Для каждого i от 1 до N - 1 двоичным поиском находим максимальное j > i такое, что игроки с i-го по j-й образуют сплоченную команду. При этом, чтобы быстро находить сумму ПП игроков с i-го по j-й, необходимо предварительно за линейное время насчитать вспомогательный массив s, в котором s[i] - сумма ПП игроков с 1-го по i-й. Тогда сумма ПП игроков с i-го по j-й sum = s[j] - s[i-1]. Выбирая максимум значений sum для всех i от 1 до N - 1 , получим искомый ответ. Время работы этого алгоритма - O(NlogN), что несколько хуже, чем в первом варианте.
Также доступны документы в формате DOC
