Разрешить превышение лимита времени для список в C++


Вход начинается с целого числа \$М, 1 \leq и М \Лек 10^5\$, количество запросов. Следующий \$Щ\$ строк, каждая из которых дает запрос. Запрос \\$текст{"х"}, 1 \leq и \Х Лек 10^9\$

Печатать результаты каждого запроса в отдельной строке. Для каждого запроса выведите целое число последнее в очереди, которая меньше, чем \Х$\$. Если не существует такого целого числа, печати \-1$\$.

Почему мой код может вызвать превышение лимита времени?

#include <iostream>
#include <list>
using namespace std;

list<int> mylist;

int searchSmall(){
    list<int>::const_iterator i;
    for (i = mylist.begin(); i != mylist.end(); ++i){
        if(*i < mylist.front()){
            return *i;
        }
    }
    return -1;
}

int main (){
  int n;
  ios_base::sync_with_stdio(false);
  cin >> n;
  while(n--){
      char e;
      cin >> e;
      if(e == 'a'){
          int q;
          cin >> q;
          mylist.push_front(q);
          cout << searchSmall() << endl;
      }
  }
  return 0;
}


Комментарии
3 ответа

Не использовать using namespace std;

Вы не скажете, на какой платформе вы или какой лимит времени будет превышен, но для работы заменить

#include <list>
list<int> mylist;

с

#include <vector>
std::vector<int> mylist;

и

mylist.push_front(q);

с

mylist.push_back(q);

и перемерить. Это будет гораздо быстрее

3
ответ дан 14 февраля 2018 в 03:02 Источник Поделиться

Это проблема классической запроса диапазона. Вы получаете такой акции, скорее всего, потому что вы используете линейную структуру данных. Зависимости от размера входных данных (в худшем случае) вам придется потратить на C*10^5 * Обработка 10^10 циклов, что, вероятно, приведет к БА в большинстве ОАО. Рассмотрите возможность использования priority_queue или двоичное дерево, для заказа данные для \$\журнал(N)\$ доступа. А именно, вы должны попытаться изменить свой list к priority_queue а затем выполните вставки и поиска с помощью приоритетной очереди/дерево. Это дает вам в худшем случае сложность времени \$о(н \зарегистрируйте N)\$.

3
ответ дан 15 февраля 2018 в 05:02 Источник Поделиться

Не используйте std::endl. Используйте простой "\n" вместо. Расследовать причины себя.

Если выше не поможет, измерения производительности на локальном компьютере и предоставить более подробную информацию, чем просто "это слишком медленно".

1
ответ дан 14 февраля 2018 в 08:02 Источник Поделиться