Problema
Todas as máquinas começam no tempo 0 e trabalham independentemente. Uma máquina com tempo t finaliza um item após t segundos, outro após 2t segundos, e assim por diante. Encontre o menor segundo inteiro em que a produção combinada delas atinge o alvo.
Implemente factory_machines(times, target).
Entrada
times: Segundos necessários para uma máquina produzir um item.
target: Número de itens completos necessários.
Saída
Retorne o número mínimo de segundos decorridos.
Restrições
1 ≤ máquinas ≤ 200.000. Cada tempo e o alvo estão entre 1 e 1.000.000.000. A resposta cabe em um inteiro assinado de 64 bits.
Exemplos
Entrada:
times = [2, 3]
target = 5
Saída esperada:
expected = 6Entrada:
std::vector<long long> times = {2, 3};
long long target = 5;
Saída esperada:
long long expected = 6;Entrada:
long[] times = new long[] {2, 3};
long target = 5;
Saída esperada:
long expected = 6;Explicação
No tempo 6, as máquinas produziram 3 + 2 = 5 itens. No tempo 5, produziram apenas 2 + 1 = 3.
Entrada:
times = [4]
target = 3
Saída esperada:
expected = 12Entrada:
std::vector<long long> times = {4};
long long target = 3;
Saída esperada:
long long expected = 12;Entrada:
long[] times = new long[] {4};
long target = 3;
Saída esperada:
long expected = 12;Explicação
Uma máquina completa seu terceiro item em 3 × 4 = 12 segundos.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Para um tempo escolhido, você pode contar quantos itens todas as máquinas juntas produziriam até lá.
Dica 2
A resposta é o menor tempo em que essa quantidade produzida alcança a meta.
Dica 3
Uma condição monotônica como essa combina bem com busca no tempo em vez de simular a produção.
Complexidade esperada
tempo O(n log T), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.