![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#51 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Премного благодарен!
Думал я где-то налажал, а тут оказывается такая хитрость нужна.. Большое спасибо, буду знать! |
![]() |
![]() |
![]() |
#52 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
![]()
В итоге то решил 321 задачу?
![]()
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
![]() |
![]() |
![]() |
#53 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Яхуууу! С возвращением
![]() ![]() Цитата:
|
|
![]() |
![]() |
![]() |
#54 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Как-то я косячу..
Задачу 321 я действительно решал.. И в 1-Ом посте это было отображено.. Однако, когда я проверял это сегодня, оказалось, что даже попыток не было.. Сейчас же показывает, что я решил ее 27.05.. Посему прошу прощения, за распространение ложной информации.. Видно плохо смотрел.. |
![]() |
![]() |
![]() |
#55 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Дамы и господа, доброе утречко!
Давай представим, что нам дали такую задачу : Дан целочисленный массив A, в котором N элементов. Необходимо переставить все отрицательные элементы в начало. Порядок не важен.. Дак вот.. Задача решается очень просто.. За O(N).. Так называемый Partition(один проход QSort) А теперь сделаем такую подлость, скажем, что порядок очень важен! И при исходных данных 4 (кол-во элементов) -1 2 -3 4 Мы должны вывести -1 -3 2 4 Задача решается снова за O(N) при достаточном кол-ве памяти.. В stl это можно сделать одной строкой.. Для этого нужен stable_partition.. НО! Найти как же его сделать без stl'я, я не смогу.. Поэтому предлагаю такой вариант (увы, я его еще не реализовал.. сейчас займусь этим.. отпишусь о результатах).. Мы снова будем использовать QSort.. Только теперь нам нужно правильно выбрать j.. Если в QSort'e мы идем с конца, то теперь нам нужно выбрать некий элемент с индексом p, такой что, кол-во отрицательныйх элементов в a[p..n] >= кол-во положительных элементов в a[1..p-1].. Не могли бы Вы разнести в пух и прах мой алгоритм, а также предложить свой! Спасибо! Удачи! |
![]() |
![]() |
![]() |
#56 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]() Цитата:
I'm learning to live...
|
|
![]() |
![]() |
![]() |
#57 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]() Цитата:
Вот.. Это должно работать за O(N) (или за O(N log N) при недостаточно кол-ве памяти).. Код:
Код:
Код:
Код:
Код:
Последний раз редактировалось Poma][a; 04.10.2014 в 13:33. |
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вопросы по БД | Rost93 | PHP | 9 | 28.06.2011 22:18 |
Вопросы по С++ | Fantazerishka | Общие вопросы C/C++ | 2 | 19.05.2010 06:52 |
Вопросы по if, else? | molodoyy | Помощь студентам | 5 | 21.03.2010 15:34 |