|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
03.09.2014, 21:41 | #51 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Премного благодарен!
Думал я где-то налажал, а тут оказывается такая хитрость нужна.. Большое спасибо, буду знать! |
18.09.2014, 15:46 | #52 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
В итоге то решил 321 задачу?
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
18.09.2014, 16:24 | #53 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Яхуууу! С возвращением Мы скучали
Цитата:
|
|
18.09.2014, 23:05 | #54 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Как-то я косячу..
Задачу 321 я действительно решал.. И в 1-Ом посте это было отображено.. Однако, когда я проверял это сегодня, оказалось, что даже попыток не было.. Сейчас же показывает, что я решил ее 27.05.. Посему прошу прощения, за распространение ложной информации.. Видно плохо смотрел.. |
04.10.2014, 09:48 | #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].. Не могли бы Вы разнести в пух и прах мой алгоритм, а также предложить свой! Спасибо! Удачи! |
04.10.2014, 13:10 | #56 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
I'm learning to live...
|
|
04.10.2014, 13:31 | #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 |