победитель |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
победитель |
passat |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
В состязаниях участвуют N (N - до 100000) спортсменов. Каждому даются три попытки. Входной файл содержит 3 строки с положением участников в каждой попытке (ни в одной из попыток невозможно двум и более человекам разделить одно место).
Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его. Найти и вывести в выходной файл количество лучших спортсменов. Реализацию напишу сам, но подскажите алгоритм. Пока просматривается следующее. Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка, задача сводится к определению количества связных областей в начале координатной прямой. Т.е. реализация в самом общем виде что-то типа такого: - считать данные в массив, где каждому спортсмену отводится по 2 позиции: на первой лучшее место, на второй худшее место - с первой позицией связываем +1, со второй - -1 (можно использовать либо пару массивов, либо один, но с несколько более сложной структурой элементов - в принципе, это сейчас не интересует) - сортируем массив (второй - по результатам первого) - осталось посчитать сумму первых +/-1 до получения первого нуля. Количество +1 дает количество победителей. Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное. Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение. |
Текстовая версия | 26.04.2024 2:49 |