Yashin_Sergey Ему самое место в "Programming Pearls" рядом с линейным алгоритмом нахождения подмассива с максимальной суммой элементов.
Yashin_Sergey В нем все правильно - я его добавил в тестовую прогу, а она проверяет результат работы, и если что не так, пишет, в какой позиции...
UbIvItS Числа в массиве b упорядочены - но это не числа из массива a, а функция от них. Массив b упорядочен по определению всегда. Но, к...
UbIvItS Алгоритм начинается с цикла с комментарием // O(N) Сначала в условнике проверяется, не опустошен ли кумулятивный массив b. Если опустошен...
Black_mirror Алгоритм - загляденье. Продолжаю медитировать ;)
Да. Тебя интересуют циклы в функции FindHeap?
В общем, потестил я этот алгоритм (чуть оптимизированный) в своей проге - на всех наборах данных работает примерно за 2.5 мс. Он даже делает LS1...
Black_mirror Мммм... работает. Похоже на кумулятивный массив, но для минимума. В общем, зачёт!!! Работает вроде так: на первой итерации...
t00x Не совсем понял, что ты имел в виду. ИМХО, на убывающей последовательности первый условник кода выполняется все время, а второй - один раз на...
Есть исходник, в котором все реализовано, но пока не смог прикрепить... Вот исходник: http://acmtest.ru/Heap.rar
Вот, написал тестовую программу: Здесь N=200000, M=10000. Random data - случайные числа Increasing data - числа упорядочены по возрастанию...
leo Двоичная куча - это такая структура данных, которая всегда идеально сбалансирована. Так что добавление и удаление всегда требуют...
Miller Rabin Скорее всего, эта задача сродни задаче сортировки сравнениями - быстрее, чем за O(N*log(M)) не получится... :\
Miller Rabin Я наверно не совсем нормально отформатировал, группы такие: 4 4 4 4 4 1 2 3 3 3 3 3 Скажи, какой будет Min/Max по твоему алгоритму,...
Miller Rabin Для данной группы да. Но потом пойдут ошибки. Еще один пример: 4 4 .......... 4 1 2 3 3 .... первая группа Обработав первую...
Имена участников (разделяйте запятой).
