Задача на дп (олимпиадная)

02.12.2012, 15:35. **Показов** 2437. **Ответов** 3

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

Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через map / set / vector / простой дин.массив. Не проходит! Понимаю, что нужно до чего-то догадаться, не выходит. Очень прошу разъяснить, а если не лень, то написать программу

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

Кликните здесь для просмотра всего текста

Ограничение по времени 1 секунда на тест

В течение всего года бассейн «Золотая рыбка» пользуется большой популярностью у спортсменов и любителей плавания. Его раздевалка состоит из бесконечного числа одноместных шкафчиков, пронумерованных натуральными числами. В течение дня постоянно занимающиеся спортсмены по прибытии занимают заранее выбранные ими шкафчики. Если выбранный спортсменом шкафчик свободен, то спортсмен занимает его. В противном случае спортсмен занимает первый свободный шкафчик с большим номером. Некоторые спортсмены заканчивают свою тренировку, исходя из индивидуального графика, и освобождают свой шкафчик досрочно. Сразу после ухода спортсмена его шкафчик становится доступным вновь пришедшему спортсмену.
Cмоделируйте работу работника reception, ответственного за распределение мест в раздевалке, и научитесь быстро сообщать прибывающим спортсменам, каким шкафчиком им следует воспользоваться.

Формат входного файла.
В первой строке входного файла число n – количество прибытий и убытий в течение дня (n<=100000). Следующие n строк содержат информацию о приходящих и уходящих спортсменах. Число k>0 обозначает, что прибыл спортсмен, который желает занять шкафчик с номером k (k<=100000). Число k<0, означает, что освобождается шкафчик под номером k, который занимал спортсмен, окончивший тренировку. (Гарантируется, что этот шкафчик не был пуст).

Формат выходного файла.
Для каждого прибывающего спортсмена выведите одно натуральное число – номер шкафчика, которым он может воспользоваться.

Пример файла входных данных и файла с результатом.

d.in

6
5
5
5
-6
5
5

d.out
5
6
7
6
8

Добавлено через 2 часа 5 минут
Никто не в силах?

Добавлено через 2 часа 6 минут
Ребят, идейку

@lemegeton · 02.12.2012, 15:52

Покажите вашу реализацию, что-ли.

02.12.2012, 16:56

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
#include <fstream>
 
 
using namespace std;
 
bool a[200001];
 
int find(int x)
{
    while (a[x]) x++;
    return x;
}
 
int main()
{
    ifstream in("d.in");
    ofstream out("d.out");
    int n,command;
    in >> n;
    memset(a, false, 200001);
    for (int i = 0; i < n; i++) {
       in >> command;
       if (command < 0) {
              command = - command;
              a[command] = false;
       }
       else if (a[command] == true) {
                 command = find(command+1);
                 a[command] = true;
                 out << command << endl;
            }
            else
            {
                a[command] = true;
                out << command << endl;
            }
    }
 
 
    return 0;
}

Не поверите, но самая быстрая моя реализация, максимальный тест 5 сек делает. Вся динамика шла за 10сек.

18.01.2013, 18:18

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

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

Mngame

	Задача на дп (олимпиадная) 02.12.2012, 15:35. Показов 2437. Ответов 3 Метки нет (Все метки) Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через map / set / vector / простой дин.массив. Не проходит! Понимаю, что нужно до чего-то догадаться, не выходит. Очень прошу разъяснить, а если не лень, то написать программу Поясню, что данная задача не входит в какую либо контрольную или еще что-то, это разбор прошлой олимпиады. За помощь огромное спасибо. Кликните здесь для просмотра всего текста Ограничение по времени 1 секунда на тест В течение всего года бассейн «Золотая рыбка» пользуется большой популярностью у спортсменов и любителей плавания. Его раздевалка состоит из бесконечного числа одноместных шкафчиков, пронумерованных натуральными числами. В течение дня постоянно занимающиеся спортсмены по прибытии занимают заранее выбранные ими шкафчики. Если выбранный спортсменом шкафчик свободен, то спортсмен занимает его. В противном случае спортсмен занимает первый свободный шкафчик с большим номером. Некоторые спортсмены заканчивают свою тренировку, исходя из индивидуального графика, и освобождают свой шкафчик досрочно. Сразу после ухода спортсмена его шкафчик становится доступным вновь пришедшему спортсмену. Cмоделируйте работу работника reception, ответственного за распределение мест в раздевалке, и научитесь быстро сообщать прибывающим спортсменам, каким шкафчиком им следует воспользоваться. Формат входного файла. В первой строке входного файла число n – количество прибытий и убытий в течение дня (n<=100000). Следующие n строк содержат информацию о приходящих и уходящих спортсменах. Число k>0 обозначает, что прибыл спортсмен, который желает занять шкафчик с номером k (k<=100000). Число k<0, означает, что освобождается шкафчик под номером k, который занимал спортсмен, окончивший тренировку. (Гарантируется, что этот шкафчик не был пуст). Формат выходного файла. Для каждого прибывающего спортсмена выведите одно натуральное число – номер шкафчика, которым он может воспользоваться. Пример файла входных данных и файла с результатом. d.in 6 5 5 5 -6 5 5 d.out 5 6 7 6 8 Добавлено через 2 часа 5 минут Никто не в силах? Добавлено через 2 часа 6 минут Ребят, идейку

@lemegeton 4903 / 2696 / 921 Регистрация: 29.11.2010 Сообщений: 5,783
	02.12.2012, 15:52
	Покажите вашу реализацию, что-ли. 0

Sunrise7463
	18.01.2013, 18:18
	если коротко-нужно составить бинарное дерево из логических переменных с проверкой условия(медиана больше номера необходимого шкафчика),где последние листья-это шкафчики,и "заполнять" ветку,когда шкафчик найден. т.е. если первый и второй шкафчик заняты их узел тоже занят т.о. когда первые 5000 шкафчиков заняты ты не перебираешь заново,а уже в самом начале дерева переходишь на правую ветку если сделаю код-пришлю(сделаю на паскале)