e-olymp 161. Роботы

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

Составьте программу, которая по заданному набору роботов обоих типов определяет, за какое минимальное время они смогут обработать определенное количество деталей.

Входные данные

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

Выходные данные

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex] [latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex] [latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex] [latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

Код программы

Решение задачи

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $ T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

One thought on “e-olymp 161. Роботы

    • Желательно добавить более детальное описание алгоритма поиска по результату или дать ссылку. Но в любом случае, пересмотрите видео. Там хорошо объясняется какого именно работа нужно подбирать на втором этапе.
    • Давайте обсудим ещё конструктивный вариант решения. Стратегия первого этапа совпадает. Но на втором этапе фактически делается тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируется самый быстрый из роботов второго типа.

    А почему я сказал, что этот подход конструктивный? Во втором цикле мы резервируем робота для обработки последней появившейся детали, потом для предпоследней и т.д. Т.е. если фиксировать эту последовательность а затем инвертировать её, то мы получим расписание (порядок) применения роботов для появляющихся после первого этапа деталей.
    Асимптотическая вычислительная сложность алгоритма $O\left(N\log \left(\max\left(N,N_a,N_b\right)\right)\right),$ т.к. для каждой из $N$ деталей за логарифмическое время работает вставка в очередь с приоритетами размера $\max\left(N,N_a,N_b\right).$
    Интересно доказать оптимальность такого подхода.

Добавить комментарий