я столкнулся со следующей проблемой, во время тестирования некоторые веб-сайт:алгоритм для обмена рабочих мест двумя исполнителями
Джон и Мэри основали J & М издательство и купил две старые принтеры оборудовать его. Теперь у них есть первая коммерческая сделка - распечатать документ , состоящий из N страниц. Похоже, что принтеры работают на скорости . Один из них создает страницу за X секунд, а другой - в Y секунд. Поэтому теперь основатели компании интересуются минимальным временем, которое они могут потратить на печать всего документа двумя принтерами.
(взято отсюда http://codeabbey.com/index/task_view/two-printers)
Я думал, что это является проблемой для жадного алгоритма, но он сказал, что N может быть до миллиарда, так что, возможно, некоторые более простое решение, которое я не мог видеть , Могу ли я прийти к решению, разделяя их пропорционально X и Y как-то?
Это, скорее всего, математический вопрос, а не вопрос алгоритма. Распределение заданий будет «YN/(X + Y) 'страницы на' X', 'XN/(X + Y)' страницы на 'Y'. Общее время будет« XYN/(X + Y) », что является оптимальным (обратите внимание, что оно эквивалентно' N/1/X + 1/Y) '. Поскольку' YN/(X + Y) 'может не быть целым числом, вы можете просто вычислить несколько значений (если« X »округляется, а« Y »округляется вниз, наоборот), тогда возьмите минимум. – justhalf
О, я вижу сейчас! наверняка пришли к тем же формулам, но я не придумал, как бороться с целыми результатами. Благодаря вам стало ясно: мне нужно закруглить их обоих, и тогда останется только одна работа, которая должна быть назначена по жадному принципу. Похоже, это может быть экстраполировано на очереди К ... Еще раз спасибо! – Alumashka
Тогда я ответил на ваш вопрос, я был бы очень признателен, если вы сможете поддержать и принять мой ответ ^^ – justhalf