Определить номер тупика, куда прибудет электричка

@liefasm · Регистрация: 20.04.2017

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

Здравствуйте. К сожалению моё решение не проходит по времени. Кто-нибудь знает как можно оптимизировать?

Задача
На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли). Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал — конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее. Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно. Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Формат ввода
Во входном файле записаны число K — количество тупиков и число N — количество электропоездов (1 ≤ K ≤ 500000, 1 ≤ N ≤ 500000). Далее идет N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время. Но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия. Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

Формат вывода
В выходной файл выведите N чисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно, чтобы организовать движение электричек согласно расписанию, в выходной файл должно быть выведено два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.

Ввод:
2 3
1 3
2 6
4 5

Выход:
1
2
1

Моё решение:

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 <fstream>
 
int main()
{
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
 
    int k = 0;
    in >> k;
 
    int n = 0;
    in >> n;
 
    int* arr = new int[k];
    for (int i = 0; i < k; i++)
    {
        arr[i] = 0;
    }
 
    int* output = new int[n];
    int offset = 0;
 
    bool state = false;
    for (int i = 0; i < n; i++)
    {
        int a = 0, b = 0;
        in >> a >> b;
        state = false;
 
        int t = 0;
        while (arr[t] >= a)
        {
            t++;
            if (t >= k)
            {
                out << "0 " << i + 1 << std::endl;
                system("pause");
                return 0;
            }
        }
 
        arr[t] = b;
        output[offset] = t + 1;
        offset++;
    }
 
    for (int i = 0; i < offset; i++)
    {
        out << output[i] << std::endl;
    }
 
    system("pause");
    return 0;
}

@burum-burum · 10.06.2019, 06:59

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

Никакие две электрички не прибывают в одно и то же время.

При этом

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

Ввод:
2 3
1 3
2 6
4 5

Первая и третья электрички приходят во время "2".

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

Время задается натуральным числом, не превышающим 109

При этом

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

1 ≤ N ≤ 500000

Электричек не может быть больше чем 109, если они не собираются прибывать в одно и тоже время.

Вы уверены, что условие верно?

@liefasm · 10.06.2019, 08:00 **[ТС]**

Первая строка ввода это - [Во входном файле записаны число K — количество тупиков и число N — количество электропоездов (1 ≤ K ≤ 500000, 1 ≤ N ≤ 500000)]

По поводу времени не знаю, но здесь указано что кол-во тупиков и поездов от 1 до 500000

@liefasm · 13.06.2019, 12:58 **[ТС]**

Проблема актуальна.

@zayats80888 · 13.06.2019, 13:25

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

К сожалению моё решение не проходит по времени

Мож system("pause") убрать?

массив output лишний, можно же сразу в файл писать

@liefasm · 13.06.2019, 13:36 **[ТС]**

Я пробовал реализовать следующую идею.

C++
1
2
3
4
5
6
7
8
9
10
struct Train
{
        Train * main = nullptr; // указатель на о
    int time; // время
 
    bool event;
 
    int index;
    int number;
};

Пусть имеется вектор events. Этот вектор состоит элементов структуры (Train) , где фигурирует время прибытия и времени отправления (всего размер вектора получается n * 2). Элемент с временем отбытия имеет указатель на элемент с временем прибытия (чтобы найти индекс его положения [индекс - тупик к которому подошел поезд, и тем самым его освободив]).

Возникли проблемы с памятью c использованием указателей.. В общем беда.

Добавлено через 2 минуты
Мне кажется что дело в цикле. Он постоянно бегает и много времени берет.

Я вот что пробовал сделать, но сегодня ошибки появились.

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
 
 
struct Train
{
    Train* main;
 
    int time;
    bool event;
 
    int index;
    int number;
    
};
 
bool cmp_test(Train a, Train b) {
    return a.time > b.time;
}
 
struct greater
{
    template<class T>
    bool operator()(T const& a, T const& b) const { return a < b; }
};
 
int main()
{
    std::vector<Train> events;
 
    int k = 0; int n = 0;
    std::cin >> k >> n;
 
    for (int i = 0; i < n; i++)
    {
        Train t1;
        int a = 0, b = 0;
        std::cin >> a >> b;
        t1.time = a; t1.event = true;
        t1.number = i+ 1;
        events.push_back(t1);
 
        Train t2;
        t2.time = b; t2.event = false;
        t2.main = &events.back();
        events.push_back(t2);
    }
 
    std::sort(events.rbegin(), events.rend(), cmp_test);
 
    int It = -1; // Итератор тупиков
    int offset = -1;
 
    std::vector<int> freelocks;
    int* output = new int[k];
 
    for (int i = 0; i < events.size(); i++)
    {
        if ((i + 1 < events.size()) && events[i].time == events[i + 1].time)
        {
            if (!events[i].event)
            {
                std::swap(events[i], events[i + 1]);
            }
        }
 
        if (events[i].event == true)
        {
            if (freelocks.size() != 0)
            {
                int v = freelocks.back();
 
                events[i].index = v;
                offset++;
 
                output[offset] = v + 1;
                freelocks.pop_back();
            }
            else
            {
                It++;
                if (It >= k)
                {
                    std::cout << "0 " << events[i].number << std::endl;
 
 
 
                    system("pause");
                    return 0;
                }
                offset++;
 
                events[i].index = It;
                output[offset] = It + 1;
 
            }
        }
        else
        {
            int v = events[i].main->index;
            freelocks.push_back(v);
 
            events[i].main = nullptr;
 
            if (freelocks.size() > 1)
                std::sort(freelocks.rbegin(), freelocks.rend(), greater());
        }
    }
 
 
    for (int i = 0; i <= offset; i++)
    {
        std::cout << output[i] << std::endl;
    }
 
    events.clear();
    return 0;
}

@7533620 · 13.06.2019, 13:49

На твоем тесте работает

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
int main()
{
    ifstream in_stream("input.txt");
    int k, n;
    in_stream >> k >> n;
    vector<int> in_time(n), out_time(n);
    for (int i = 0; i < n; ++i)
        in_stream >> in_time[i] >> out_time[i];
    set<int> free_garages;
    for (int i = 1; i <= k; ++i)
        free_garages.insert(i);
 
    vector<int> ans(n);
    multiset<pair<int, int>> train_set;
    for (int i = 0; i < n; ++i)
    {
        for (auto j = train_set.begin(); j != train_set.end();)
            if (j->first < in_time[i])
            {
                for (auto x = j; x != train_set.end() && x->first == j->first; ++x)
                    free_garages.insert(x->second);
                j = train_set.erase(j);
            }
            else
                break;
        ans[i] = *free_garages.begin();
        train_set.insert({out_time[i], *free_garages.begin()});
        free_garages.erase(free_garages.begin());
    }
 
    ofstream out_stream("output.txt");
    for (auto e : ans)
        out_stream << e << endl;
    return 0;
}

@liefasm · 13.06.2019, 14:01 **[ТС]**

Input:
1 2
2 5
5 6

Output:
0 2

@7533620 · 13.06.2019, 14:07

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

Input:
1 2
2 5
5 6
Output:
0 2

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
int main()
{
    ifstream in_stream("input.txt");
    int k, n;
    in_stream >> k >> n;
    vector<int> in_time(n), out_time(n);
    for (int i = 0; i < n; ++i)
        in_stream >> in_time[i] >> out_time[i];
    set<int> free_garages;
    for (int i = 1; i <= k; ++i)
        free_garages.insert(i);
 
    vector<int> ans(n);
    multiset<pair<int, int>> train_set;
    for (int i = 0; i < n; ++i)
    {
        for (auto j = train_set.begin(); j != train_set.end();)
            if (j->first < in_time[i])
            {
                for (auto x = j; x != train_set.end() && x->first == j->first; ++x)
                    free_garages.insert(x->second);
                j = train_set.erase(j);
            }
            else
                break;
        if (!free_garages.size())
            return (ofstream("output.txt") << 0 << endl << i + 1, 0);
        ans[i] = *free_garages.begin();
        train_set.insert({out_time[i], *free_garages.begin()});
        free_garages.erase(free_garages.begin());
    }
 
    ofstream out_stream("output.txt");
    for (auto e : ans)
        out_stream << e << endl;
    return 0;
}

@liefasm · 13.06.2019, 14:14 **[ТС]**

К сожалению это решение не проходит по времени.. У меня была такая идея но я не могу её реализовать из-за ошибок с памятью.

Есть структура:

C++
1
2
3
4
5
6
7
8
9
10
struct Train
{
    Train* main = NULL; // Указатель на элемент структуры Train - с временем прибытия
 
    int time; // Время [прибытия или отбытия]
    bool event; // если true - то этот объект за прибытие, false - отбытие
 
    int index; // Индекс - номер тупика в котором стоит поезд
    int number; // Номер поезда
};

В вектор Events загружаются элементы типа Train с временем прибытия и времени отправления. Если объект с временем отправления - то он имеет связь через Train * main с объектом прибытия (чтобы в дальнейшем удалить его из тупика.

В дальнейшем после заполнения нужно отсортировать вектор Events по возрастанию. В дальнейшем основной алгоритм проходит по этому вектору и выполняет определенные действия (добавить в тупик, изъять из тупика и прочее).

Если поезд был убран из тупика, он индекс (номер тупика в котором он находился) попадается в вектор freelocks, который постоянно сортируется по возрастанию и в случае добавления нового поезда (если freelocks не пуст) - поезд попадает на тупик получаемый путём исполнения freelocks.back() и потом для удаления тупика из списка свободных тупиков - freelocks.pop_back().

У меня возникли проблемы с munmap_chunk(): invalid pointer: 0x0000000000a85290 ***...

Добавлено через 3 минуты
Всё прошло. Спасибо.. Я вижу Вы использовали различные возможности STL. К сожалению я не имею такой багаж познания в STL и использовал какие-то тупые идеи ;(

@7533620 · 13.06.2019, 14:15

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

который постоянно сортируется по возрастанию

Такое медленее чем решение с сетами

@zayats80888 · 13.06.2019, 15:09

liefasm, через map попробуй(не отлаживал)

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
#include <iostream>
#include <fstream>
#include <unordered_map>
 
int main()
{
    std::ifstream ifs{ "input.txt" };
    int k, n;
    ifs >> k >> n;
    
    std::ofstream ofs{ "output.txt" };
    std::unordered_map<int, int> m;
    for (int to{}, from{}, garage{ 1 }, idx{1}; ifs >> to >> from; ++idx)
    {
        auto mp = m.find(to - 1);
        if (mp != m.end())
        {
            m.insert(std::make_pair(from, mp->second));
            ofs << garage << std::endl;
            std::cout << mp->second << std::endl;
            m.erase(mp);
        }
        else
        {
            if (garage > k)
            {
                ofs << '0 ' << idx;
                break;
            }
            m.insert(std::make_pair(from, garage));
            std::cout << garage << std::endl;
            ++garage;
        }
    }
}

@liefasm · 13.06.2019, 15:13 **[ТС]**

Всё давно уже прошло. Всем спасибо.

Новые блоги и статьи Все статьи Все блоги /
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .

@liefasm 0 / 0 / 0 Регистрация: 20.04.2017 Сообщений: 15
	10.06.2019, 08:00 [ТС]
	Первая строка ввода это - [Во входном файле записаны число K — количество тупиков и число N — количество электропоездов (1 ≤ K ≤ 500000, 1 ≤ N ≤ 500000)] По поводу времени не знаю, но здесь указано что кол-во тупиков и поездов от 1 до 500000 0

@liefasm 0 / 0 / 0 Регистрация: 20.04.2017 Сообщений: 15
	13.06.2019, 12:58 [ТС]
	Проблема актуальна. 0

@liefasm 0 / 0 / 0 Регистрация: 20.04.2017 Сообщений: 15
	13.06.2019, 14:01 [ТС]
	Input: 1 2 2 5 5 6 Output: 0 2 Миниатюры 0

@liefasm 0 / 0 / 0 Регистрация: 20.04.2017 Сообщений: 15
	13.06.2019, 15:13 [ТС]
	Всё давно уже прошло. Всем спасибо. 0

Определить номер тупика, куда прибудет электричка

Решение