Дайте совет по оптимизации задачи

@LanVanDance · Регистрация: 09.09.2018

Студворк — интернет-сервис помощи студентам

Студенты и преподаватели очень любят столовую. Так как посетителей много, в столовой часто образутся очень длинные очереди. Студенты при посещении столовой должны вставать в конец очереди. Преподаватели встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром. Попросили вас написать программу, которая бы отслеживала правильное расположение посетителей в очереди.

Формат ввода
В первой строке входных данный записано число N (1 ≤ N ≤ 106) - количество запросов к программе.
Следующие N строк содержат описание запросов в формате:
• "+ i" - студент с номером i (1 ≤ i ≤ N) встает в конец очереди.
• "* i" - преподаватель с номером i встает в середину очереди.
• "-" - первый посетитель из очереди обслуживается работниками столовой.
Гарантируется, что на момент такого запроса очередь не пуста.

Формат вывода
Для каждого запроса типа "-" программа должна вывести номер посетителя, который должен быть обслужен работниками столовой.

Пример:
Ввод:
12
+ 1
+ 2
* 3
-
* 4
+ 5
-
* 6
-
-
-
-

Вывод
1
3
4
2
6
5

Дело в том, что если кол-во людей привышает 400000, то время выполнение программы дольше секунды..

Вот моё решение. Оно конечно тривиальное, но у меня нет идей в её оптимизации.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <deque>
#include <string>
#include <fstream>
#include <iterator>
 
 
int main()
{
    std::ifstream file;
    file.open("input.txt");
 
    int n = 0;
    file >> n;
 
    std::deque<int> q;
 
    while (!file.eof())
    {
        char ch;
        file >> ch;
        if (file.eof()) break;
        else
        {
            switch (ch)
            {
            case '+':
            {
                int v;
                file >> v;
 
                q.push_back(v);
                continue;
            }
            case '*':
            {
                int v;
                file >> v;
                int mid = q.size() / 2;
                q.insert(q.end() - mid, v);
                continue;
            }
            case '-':
            {
                std::cout << q.front() << std::endl;
                q.pop_front();
                continue;
            }
            }
        }
    }
 
    system("pause");
    return 0;
}

[!] Задачу нужно решать с помощью стека, очереди, дека, очереди с приоритетом.

Добавлено через 21 минуту
Переписал листинг. Выше был старый.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <deque>
#include <string>
#include <fstream>
#include <iterator>
 
void pushToMiddle(std::deque<int>& q, int mid, int v)
{
    std::deque<int> temp;
    for (int i = 0; i < mid; i++)
    {
        temp.push_back(q.back());
        q.pop_back();
    }
 
    q.push_back(v);
 
    while (!temp.empty())
    {
        q.push_back(temp.back());
        temp.pop_back();
    }
}
 
int main()
{
    std::ifstream file;
    file.open("input.txt");
 
    int n = 0;
    file >> n;
 
    std::deque<int> q;
 
    while (!file.eof())
    {
        char ch;
        file >> ch;
        if (file.eof()) break;
        else
        {
            if (ch == '-' && q.size() == 0) continue;
            switch (ch)
            {
            case '+':
            {
                int v;
                file >> v;
 
                q.push_back(v);
                continue;
            }
            case '*':
            {
                int v;
                file >> v;
                int mid = q.size() / 2;
 
                pushToMiddle(q, mid, v);
                continue;
            }
            case '-':
            {
                std::cout << q.front() << std::endl;
                q.pop_front();
                continue;
            }
            }
        }
    }
 
    system("pause");
    return 0;
}

@zayats80888 · 28.04.2019, 07:57

Ну не уверен, что оптимально(зависит от размера очереди и частоты появления преподавателей), но можно попробовать с двумя очередями:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    std::deque<int> front, back;
    char ch;
    while (in >> ch)
    {
        int num;
        switch (ch)
        {
        case '+':
            in >> num;
            back.push_back(num);
            if (back.size() > front.size())
            {
                front.push_back(back.front());
                back.pop_front();
            }
            break;
        case '*':
            in >> num;
            if (front.size() > back.size())
                back.push_front(num);
            else
                front.push_back(num);
            break;
        case '-':
            std::cout << front.front() << std::endl;
            front.pop_front();
            if (front.size() < back.size() && !back.empty())
            {
                front.push_back(back.front());
                back.pop_front();
            }
        }
    }

@XLAT · 28.04.2019, 14:36

zayats80888,
это самое то,
разрезать очередь по середине на две очереди, именно там и будут вставляться преподы.

IGPIGP · 28.04.2019, 19:36

Может со списком побыстрее получится, хотя выглядит монструозненько:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <list>
#include <cstring>
#include <cassert>
using namespace std;
class queue_
{
public:
    void push_back(int ad)
    {
        qq.push_back(ad);
            if(qq.size()%2)
            {
               --middle;
            }else
                ++middle;
 
    }
 
    void insert_middle(int ins)
    {
 
        if(qq.size()%2)
        {
typename list<int>::iterator ins_it=middle;
            ++ins_it;
             middle=qq.insert(ins_it, ins);
        }else
         middle=qq.insert(middle, ins);
    }
 
    void pop(int dummy=0)
    {
        if(qq.size())
        {
           done.push_back(*qq.begin());
           qq.erase(qq.begin());
           if(qq.size()%2==0)
           {
              ++middle;
           }
 
        }
    }
    void request_handle(const char* cstr_req){
        if((cstr_req[0] == '-')) return pop();
        if((cstr_req[0] == '+')) return push_back(cstr_req[2]-'0');
        if((cstr_req[0] == '*')) return insert_middle(cstr_req[2]-'0');
        assert(!strcmp(cstr_req, "invalid meta command in request"));
    }
    queue_()
        :middle(qq.end())
        ,cqq(qq)
        ,cdone(done)
    {}
private:
    list<int> qq;
     list<int> done;
    typename list<int>::iterator middle;
public:
 const list<int>& cqq;
 const list<int>& cdone;
};
 
int main()
{
 const char * requests[]=
 {"+ 1", "+ 2", "* 3", "-","* 4","+ 5","-","* 6", "-", "-", "-", "-"};
 queue_ qreq;
 for(auto req:requests)
 {
     qreq.request_handle(req);     
 }
 cout<<"the whole treated queue is:\n";
for(const auto number:qreq.cdone)cout<<number<<endl;
for(const auto number:qreq.cqq)cout<<number<<endl;
cin.get();
return 0;
}

@LanVanDance · 01.05.2019, 01:01 **[ТС]**

Ваш код отлично проходит тесты, но.. В одном тесте происходит Runtime Error. Причина неизвестна, буду просить логи..

Не можете предположить причину данного поведения?

Полные логи входа получить не могу, слишком много. Из того что показано - всё проходит без ошибок.

IGPIGP · 01.05.2019, 09:21

Сообщение от LanVanDance

В одном тесте происходит Runtime Error. Причина неизвестна, буду просить логи..
Не можете предположить причину данного поведения?

Причина в ошибке.
Если такое объяснение не исчерпывает вашего интереса, покажите сообщение от системы. Можно брэйк пойнтами прощупать место где это происходит и попробовать захватить данный участок в try блок и отловить.

Добавлено через 13 минут
LanVanDance, сейчас уже не вспомнить, - надо снова погрузиться, а времени нет. Проверьте инкремент итератора середины. Когда он указывает на конец этого делать не стоит, но такой проверки нет. то есть, при входе в блок она есть но перед инкрементацией её нет, а там есть действия в блоке, которые могут (возможно) сделать такую операцию опасной..

при входе в блок она есть

и то косвенная - проверка размера списка. Вторая проверка на чётность не катит - ноль, чётное число.
Поисследуйте это и может быть этого хватит.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@XLAT Just Do It! 4211 / 2668 / 655 Регистрация: 23.09.2014 Сообщений: 9,077 Записей в блоге: 3
	28.04.2019, 14:36
	zayats80888, это самое то, разрезать очередь по середине на две очереди, именно там и будут вставляться преподы. 0

@LanVanDance 1 / 1 / 0 Регистрация: 09.09.2018 Сообщений: 5
	01.05.2019, 01:01 [ТС]
	Ваш код отлично проходит тесты, но.. В одном тесте происходит Runtime Error. Причина неизвестна, буду просить логи.. Не можете предположить причину данного поведения? Полные логи входа получить не могу, слишком много. Из того что показано - всё проходит без ошибок. 0

Дайте совет по оптимизации задачи

Решение