Factory Machines

Pista 1

Si cambiamos el tiempo total, ¿cómo se ve afectada la cantidad de productos fabricados?

Pista 2

Comparado con el número de productos deseado que da la entrada, ¿cuántos productos se fabrican cuando el tiempo total es menor o mayor que la respuesta real?

Solución

Explicación

En este problema nos dan $n$ máquinas y nos piden el tiempo mínimo que estas máquinas necesitan trabajar para crear $t$ productos de modo que la $i$ -ésima máquina crea un producto en tiempo $k_i$ .

Búsqueda binaria

Observemos que el tiempo necesario para crear al menos $x$ productos es monótono. En otras palabras, si las máquinas dadas pueden crear $x$ productos en tiempo $y_1$ , entonces las mismas máquinas pueden crear al menos $x$ productos en tiempo $y_2 > y_1$ . Usando esta propiedad, podemos hacer búsqueda binaria sobre la respuesta. Léase este módulo para más información.

Para algún valor sobre el que hacemos búsqueda binaria, $ans$ , nos queda la tarea de comprobar si podemos crear $t$ productos en tiempo $ans$ . Para ello, observemos que es óptimo que todas las máquinas trabajen a la vez. Entonces, en tiempo $ans$ , la máquina $i$ puede crear $\lfloor \frac{ans}{k_i} \rfloor$ productos.

En total, las $n$ máquinas pueden crear $\sum_{i=1}^{n} \lfloor \frac{ans}{k_i} \rfloor$ productos. Si esta suma $\geq t$ , entonces $ans$ es válido.

Implementación

Complejidad temporal: $\mathcal{O}(N \log T)$ , donde $T$ es el mayor tiempo que necesitamos considerar.

C++JavaPython


#include <climits>
#include <iostream>
#include <vector>
 
using std::vector;
 
 
int main() {
	int n;
	long long t;
	std::cin >> n >> t;
	vector<int> k(n);
 
	int mn = INT_MAX;
	for (int &x : k) {
		std::cin >> x;
		mn = std::min(mn, x);
	}
 
	long long lo = 0;
	long long hi = mn * t;
	long long res = 0;
	while (lo <= hi) {
		long long mid = (lo + hi) / 2;
		long long sum = 0;
		for (int i = 0; i < n; i++) {
			sum += (mid / k[i]);
			if (sum >= t) { break; }
		}
 
		if (sum >= t) {
			res = mid;
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
 
	std::cout << res << std::endl;
}


import java.io.*;
import java.util.*;
 
public class FactoryMachines {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();  // number of machines
		int goal = io.nextInt();
 
		int[] machines = new int[n];
		for (int i = 0; i < n; i++) { machines[i] = io.nextInt(); }
 
		long lo = 0;
		long hi = (long)1e18;
		long ans = 0;
		while (lo <= hi) {
			long mid = (lo + hi) / 2;
 
			long n_produced = 0;
			for (int machine : machines) {
				n_produced += mid / machine;
				// Break as soon as we hit our goal
				if (n_produced >= goal) { break; }
			}
 
			if (n_produced >= goal) {
				ans = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


_, goal = map(int, input().split())
machines = list(map(int, input().split()))
 
lo = 0
hi = 10**18
ans = 0
while lo <= hi:
	mid = (lo + hi) // 2
 
	n_produced = 0
	for machine in machines:
		n_produced += mid // machine
 
	if n_produced >= goal:
		ans = mid
		hi = mid - 1
	else:
		lo = mid + 1
 
print(ans)