2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение31.05.2019, 17:54 
Слияние фибоначчевых куч делается за $O(1)$.
С одной кучей конечно проще и может быть даже быстрее.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение31.05.2019, 22:41 
Одна сортировка массива с правильным ключём + потом один проход по этому массиву и заполнение другого массива. О чём тут думать?
Хотя, да, есть одна тонкость. Нужно ещё хранить сливаемые множества заполненных интервалов, для каждого заполненного интервала храним его текущую левую границу. Представляем множество заполненных интервалов в виде леса со сжатием путей. Структуру организуем в рамках одного массива по дням. Берём работу с максимальной стоимостью с наиболее ранним дедлайном среди работ равной стоимости, и размещаем её в наиболее поздний доступный для этого дедлайна день. Всё.

Как упрощение и ускорение: размещаем корень дерева, представляющего заполненный интервал, в самый левый элемент интервала.

PS Можно ли к этой задаче свести задачу сортировки?

-- 31.05.2019, 23:28 --

blueboar2 в сообщении #1396541 писал(а):
Файл читается по байтам тоже для быстроты.
Это вы фигнёй страдаете.

-- 31.05.2019, 23:30 --

blueboar2 в сообщении #1396541 писал(а):
Что еще ускорить я не знаю.
Это у вас задача в рамках курса программироавния? Вы теорию сложности алгоритмов изучали? Изучили?

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение31.05.2019, 23:43 
Аватара пользователя
"ключом".

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение31.05.2019, 23:45 
Munin в сообщении #1396967 писал(а):
"ключом".

Это авторский стиль. :mrgreen:
Всё равно править поздно.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 00:11 
realeugene
Хитро придумано! (просто заполнять набор промежутков самыми дорогими задачами, обновляя для каждого промежутка ссылку на ближайший ещё не заполненный(скорее всего) промежуток)
Это наверно самое простое решение, т.к. требуется всего 2 сортировки (по времени и по стоимости) и простейшая структура данных.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 01:10 
Аватара пользователя
А первая сортировка нафига?...

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 09:27 
Чтобы быстрее находить ближайшую свободную дырку.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 11:53 
feedinglight в сообщении #1396972 писал(а):
т.к. требуется всего 2 сортировки (по времени и по стоимости)
Я тоже не понял как с двумя сортировками.

Подробнее. Алгоритм жадный - мы должны отсортировать работы в список, из которого берём их по одному последовательно. Работы берём в порядке убывания стоимости, работы одинаковой стоимости берём в порядке возрастания дедлайна, порядок работ одной стоимости с одинаковым дедлайном нам не важен. Это одна сортировка, которая, к тому же, может быть и неустойчивой. Какой-нибудь qsort для случайных входных данных вполне подойдёт, если преподаватель не слишком злой.

Отсортировав работы, мы распределяем эти работы по дням. Берём очередную работу из списка и распределяем её в наиболее поздний свободный день перед дедлайном. Но день перед дедлайном уже может быть занят ранее распределёнными работами. И дни перед ним. И нужно быстро найти по дедлайну ближайший свободный день перед отрезком занятых дней, которому принадлежит день перед дедлайном. Для этого храним массив с лесом занятых дней, в котором непрерывные последовательности занятых дней объединены в одно дерево. По каждому дню храним день его предка в дереве. Распределяя очередную работу, берём день перед дедлайном и ищем, какому дереву-интервалу он соответствет. При поиске корня дерева не забываем путь сжимать. После добавления новой работы в свободный день объединяем этот занятый день с множествами-деревьями слева и справа от него, если интервалы слились. Вы правильно подсказали сделать корнем дерева первый свободный день слева от занятого интервала. Тогда вообще ещё проще: каждому свободному дню соответствует одно дерево в этом лесу, первоначально в массиве предков инициализируем каждый элемент своим собственным индексом, а у самого левого занятого интервала корень дерева делаем фиктивным, например, с индексом -1. Если очередная распределяемая работа попала в этот интервал, её выкидываем.

А как решить задачу со второй сортировкой?

UPD Хотя нет, сорри, я налажал. Объединять деревья нужно по рангам, добавляя меньшее дерево к большему. То есть, для каждого дерева нужно хранить ещё и его ранг (длину интервала), и корень дерева мы не можем выбирать произвольно, так как меньшее дерево нужно добавлять к большему. В корне индекс предка, действительно, можно переиспользовать в качестве дополнительной связанной с деревом информации - индекса свободного элемента слева от интервала, но это уже не принципиально.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 13:05 
Аватара пользователя
realeugene в сообщении #1397015 писал(а):
мы должны отсортировать работы в список

Зачем?

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 13:09 
Geen в сообщении #1397039 писал(а):
Зачем?
Чтобы рассматривать работы в требуемом для жадного алгоритма порядке. Это, просто, сортировка списка работ, и её проще выполнить заранее первым этапом.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 13:26 
Аватара пользователя
Зачем деревья (т.е. я понимаю зачем, но можно же сильно проще), зачем слияние куч (совсем не понимаю зачем)?

Заводим кучу работ (изначально пустую). Бежим по работам в порядке убывания дедлайна. Если дедлайн текущей работы меньше дедлайна предыдущей - то вынимаем из кучи самые дорогие работы по разности дней. Кладем текущую работу в кучу.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 16:03 
mihaild в сообщении #1397043 писал(а):
то вынимаем из кучи самые дорогие работы по разности дней.
Это как? Не понял критерий.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 17:25 
Аватара пользователя
Если у текущей работы дедлайн $n$, а у предыдущей просмотренной $m$, то вынимаем из кучи $m-n$ работ (или сколько есть, если есть меньше).
Ну и добавляем фиктивную работу с дедлайном 0 для простоты.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 17:52 
mihaild в сообщении #1397097 писал(а):
Если у текущей работы дедлайн $n$, а у предыдущей просмотренной $m$, то вынимаем из кучи $m-n$ работ (или сколько есть).
Да, так проще всего.

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

Да, хорошая идея. В куче для каждого дня находятся только те работы, которые ещё не распределены и которые можно выполнить в этот день. В последний день выполняем самую дорогую работу, у которой не кончился дедлайн. Дальше по индукции.

 
 
 
 Re: Задача на C#, не проходит по требуемому времени
Сообщение01.06.2019, 18:04 
Аватара пользователя
Используется синтаксис Python
jobs.append(TJob(deadline=0, price=None))
jobs.sort(key=lambda job: job.deadline, reverse=True))
h = THeap()
result = 0
prev_deadline = 10**100
for deadline, price in jobs:
  while (not h.empty()) and (prev_deadline > deadline):
    result += h.pop_min()
    prev_deadline -= 1
   prev_deadline = deadline
   h.add(price)

(Оффтоп)

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


-- 01.06.2019, 18:05 --

realeugene в сообщении #1397108 писал(а):
Потом в цикле для каждой даты с конца в сторону начала добавляем пачкой в кучу все работы из кармана, соответствущего этой дате. И затем вынимаем из кучи работу с максимальной стоимостью, если куча не пустая, выполняя эту работу в этот день.

Только нужно аккуратно - нужно пропускать большие промежутки, в которых нам нечего делать. Иначе если есть работа с дедлайном $10^{10}$, перебор всех дней будет долгим...

 
 
 [ Сообщений: 52 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group