Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $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]

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

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);
	}
}

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
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

e-olymp 161. Роботы