![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 30.10.2010
Сообщений: 7
|
![]()
Здравствуйте. Помогите пожалуйста с алгоритмом для решения следующей задачи:
Я могу сделать только перебором, но в худшем случае, что я смог придумать, перебор работает за 8-9 сек, а надо уложиться в 2 сек. |
![]() |
![]() |
![]() |
#2 |
Форумчанин
Регистрация: 07.11.2011
Сообщений: 100
|
![]() |
![]() |
![]() |
![]() |
#3 | |
Форумчанин
Регистрация: 15.01.2010
Сообщений: 948
|
![]()
А как её решать-то БЕЗ перебора?! Другое дело, что перебор перебору - рознь...
Цитата:
![]() |
|
![]() |
![]() |
![]() |
#4 |
Форумчанин
Регистрация: 07.11.2011
Сообщений: 100
|
![]() |
![]() |
![]() |
![]() |
#5 | ||
Регистрация: 30.10.2010
Сообщений: 7
|
![]() Цитата:
Цитата:
Я же сказал, что в худшем случае, который я смог придумать. Правда я не сказал, что n <= 10^5. |
||
![]() |
![]() |
![]() |
#6 |
Форумчанин
Регистрация: 15.01.2010
Сообщений: 948
|
![]() |
![]() |
![]() |
![]() |
#7 |
Регистрация: 30.10.2010
Сообщений: 7
|
![]()
Код, который должен решать задачу:
Код:
Код:
|
![]() |
![]() |
![]() |
#8 |
Форумчанин
Регистрация: 15.01.2010
Сообщений: 948
|
![]() Код:
1. Двукратное сокращение времени, благодаря переходу от списка к массиву, и ещё двукратное - после небольшого изменения алгоритма (хотя сложность, по-прежнему O(n^2)). Вот Вам вожделенные 2 секунды вместо 8. 2. Либо я чего-то не понял, либо у Вас data->numOfIntersections первый раз используется непроинициализированным, поэтому я эту доп. проверку у Вас в Варианте I просто выбросил ![]() 3. Написал new() - напиши delete()! Когда ж в вас преподаватели это вобьют наконец?!.. ![]() 4. Всё это работает только если для каждой хорды меньший номер вершины стоит первым, а больший - вторым. Для файла Код:
5. Про O(n*log(n)) - это надо подумать... Последний раз редактировалось Vago; 25.03.2012 в 23:17. Причина: ptBeg0 в CheckVago() оставалась от игр с допущением 4 |
![]() |
![]() |
![]() |
#9 | ||
Регистрация: 30.10.2010
Сообщений: 7
|
![]()
Спасибо, постараюсь сегодня просмотреть код.
Цитата:
Цитата:
Мне вот посоветовали использовать дерево отрезков. Только я не понимаю, как её здесь использовать. Если не ошибаюсь, эта структура позволяет искать минимум из элементов с индексами из отрезка [left, right], а также модифицировать i-й элемент за O (log(n)). |
||
![]() |
![]() |
![]() |
#10 |
Регистрация: 30.10.2010
Сообщений: 7
|
![]() |
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача про рекурсию | NIKI18 | Общие вопросы C/C++ | 1 | 19.12.2011 20:35 |
Задача про списки | Алекс12345 | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 20.08.2011 19:33 |
Задача про банк..... | Васильева Зинаида | Помощь студентам | 3 | 07.11.2010 13:05 |
задача про муху | DarkMage | Общие вопросы C/C++ | 1 | 14.09.2010 20:59 |