Задача
На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $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] |
Код программы
|
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 |
import java.util.*; public class Main { private static class Pair{ int a, b; public Pair(int a, int b) { this.a=a; this.b=b; } } public static void main (String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int na = scanner.nextInt(); int[] A = new int[na]; int[] times = new int[n]; PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a); for(int i=0; i<na; i++) { A[i] = scanner.nextInt(); q.add(new Pair(A[i], A[i])); } for(int i=0; i<n; i++) { Pair pair=q.poll(); times[i]=pair.a; q.add(new Pair(pair.a+pair.b, pair.b)); } q.clear(); int nb = scanner.nextInt(); int[] B = new int[nb]; int max_time=0; for(int i=0; i<nb; i++) { B[i] = scanner.nextInt(); q.add(new Pair(B[i], B[i])); } for(int i=n-1; i>=0; i--) { Pair pair=q.poll(); times[i]+=pair.a; q.add(new Pair(pair.a+pair.b, pair.b)); if(times[i]>max_time) max_time=times[i]; } System.out.println(max_time); } } |
Решение задачи
Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
На втором этапе фактически делаем тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируем самый быстрый из роботов второго типа.
Теперь оценим сложность работы алгоритма. Для каждой из $n$ деталей работает логарифмическая вставка в очередь с приоритетом. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log n)$.
Ссылки
Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова: