Форум программистов, компьютерный форум CyberForum.ru

Программа не проходит тесты по времени, посоветуйте как исправить - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Курсовая ( нужно задать клас контейнер очередь с сортировкою ) http://www.cyberforum.ru/cpp-beginners/thread1057452.html
есть такой основной код , но он не мой !! а так как сегодня нужно сдать , я пользуюсь им , но не могу написать файл.h к нему !! подскажите пожалуйста #include "queue.h" queue::queue(void) { head=NULL;//головы нет tail=NULL;//хвоста нет length=0;//длинна - 0 }
C++ Как в виде подпрограммы ввести массив треугольника? Как в виде подпрограммы ввести массив треугольника? http://www.cyberforum.ru/cpp-beginners/thread1057429.html
C++ динамические структуры данных
Добрый день помогите с задачкой Дана вещественная квадратная матрица порядка N. Получить целочисленную квадратную матрицу, в которой элемент равен 1, если соответствующий ему элемент исходной матрицы больше элемента, расположенного на главной диагонали. и равен 0 в противном случае.
Нахождение минимального количества букв подряд C++
Дана строка, найти наименьшее идущее подряд количество букв, но не менее 2 очень нужна ваша помощь
C++ выделение из массива четных и нечетных чисел http://www.cyberforum.ru/cpp-beginners/thread1057404.html
Люди подскажите пожалуйста, задание надо переделать в "к каждому нечетному числу массива прибавить полусумму всех четных" #include "stdafx.h" #include <iostream> #include <deque> #include <ctime> #include <cstdlib> #include <conio.h> #define N 50
C++ Работа с сокетами Помогите создать приложение клиент - сервер, в Visual Studio 2010 C++, проект Win32 если можно с объяснением как создать проект и куда записать код программы. подробнее

Показать сообщение отдельно
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 34
26.12.2013, 12:48     Программа не проходит тесты по времени, посоветуйте как исправить
Добрый день, не могли бы вы подсказать по задаче. Имеется круг с целыми числами от 1 до n. Числа можно или занимать или освобождать если оно было занято. Во входном потоке задана последовательность запросов в виде чисел. Если число x > 0, то это запрос на занятие числа x на круге. Если число x уже занято, то берется следующее число по часовой стрелке, и выводится номер занятого по факту числа. Если все занято выводится -1. Если x < 0, тогда если число |x| занято оно освобождается и выводится 0. Если свободно, тогда выводится -2. Всего запросов m штук. В первой строке заданы n и m (от 1 до 100000), затем m запросов. Время одна секунда.
Пример.
3 6
1 1 1 1 -1 -1
1 2 3 -1 0 -2

Я реализовал двумя способами:
1) Дерево поиска, если пришел запрос x > 0. Я проверяю есть ли заданное число в дереве, если нет тогда я его туда добавляю, если есть увеличиваю на 1 и так максимум n раз. Если x < 0, тогда ищу в дереве |x| если есть удаляю.
2) Я завел булев массив, если число не занято, то на его месте true, если занято false.

Оба решения не проходят по времени. Тема до этого была деревья поиска. Но не факт, что в решении будет дерево.
Как вы думаете:
1) Тут другое решение или корявая реализация?
2) Имеет ли смысл переписывать рекурсивный поиск в дереве на не рекурсивный?
3) Имеет ли смысл написать процедуру, которая в начале ищет в дереве число, если нашла, то она начинает из данного узла искать следующее число и т. д.
4) Можете предложить еще какие-нибудь решения?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 17:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru