Book Allocation Problem

Q: O Problema de Alocação de Livros é o mesmo que a Soma Máxima de um Array Dividido?

Sim. Ambos dividem um array em um número fixo de blocos contíguos não vazios e minimizam a maior soma de bloco, e a mesma busca binária com a mesma verificação gulosa resolve ambos. A versão do livro adiciona o caso -1 .

Q: Qual é a complexidade de tempo do Problema de Alocação de Livros?

Tempo O(n log S) e espaço extra O(1) , em que n é o número de livros e S é o total de páginas. Cada limite testado custa uma passagem pelos livros, e a busca testa cerca de log2 S limites: 29 em uma estante com 5 × 10^8 páginas.

Q: Quando é impossível alocar os livros?

Somente quando houver mais alunos do que livros, pois cada aluno precisa de pelo menos um livro. Com livros suficientes, qualquer bloco de dois ou mais livros pode dar seu último livro a um aluno que não tenha nenhum, até que todos tenham um.

MédioBusca binária Guloso

+10

Uma estante contém livros em uma ordem fixa, e pages[i] é o número de páginas do livro i. Distribua os livros entre students estudantes: cada estudante recebe uma sequência contínua de livros vizinhos, pelo menos um livro cada, e cada livro vai para exatamente um estudante. A carga de um estudante é o total de páginas que ele recebe.

Retorne o menor valor possível da carga mais pesada. Se houver mais estudantes do que livros, retorne -1.

Função

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: a quantidade de páginas de cada livro, na ordem da estante
studentsinteger: o número de estudantes que compartilham os livros
Retornainteger: a menor carga máxima possível, ou -1 quando há mais estudantes do que livros

Restrições

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Retorne -1 quando students > pages.length.

Exemplos

Entrada: pages = [25, 40, 15, 30, 50]students = 3
Saída: 65
Explicação: Distribua [25, 40], [15, 30] e [50]: cargas de 65, 45 e 50. Um limite de 64 falha: a distribuição resulta em [25], [40, 15], [30], [50], quatro estudantes.

Entrada: pages = [10, 20]students = 3
Saída: -1
Explicação: Dois livros não podem dar um livro para cada um dos três alunos, então a resposta é -1.

Para ir além

Prove que a quantidade média de livros por prateleira, arredondada para cima, somada ao livro mais grosso é sempre um limite funcional. Quantas verificações esse limite superior economiza em uma estante de livros finos?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Há muitas maneiras de dividir a prateleira, mas testar um limite de páginas é barato: distribua os livros na ordem em que estão na prateleira, passando para o próximo aluno quando um livro ultrapassaria o limite, e conte os alunos. Um limite maior nunca exige mais alunos, então os limites que funcionam formam uma sequência, e a busca binária encontra onde ela começa.

Aumente o limite de páginas de uma em uma

Correta, mas não termina nos maiores testes

Intuição

Comece em L = max(pages), já que alguém vai carregar o livro mais grosso, e aumente L uma página por vez até que a contagem gulosa caiba em students. Todos os limites menores falharam, então o primeiro que funciona é a resposta. No primeiro exemplo, todos os limites de 50 a 64 exigem quatro estudantes, e 65 exige três: 16 verificações.

A resposta pode ser a prateleira inteira: um estudante e 5000 livros de 10^5 páginas significam cerca de 5 × 10^8 limites, cada um exigindo uma passagem pelos 5000 livros. Na coluna de tempo, A é a resposta e m é o livro mais grosso.

Algoritmo

Se students > pages.length, retorne -1.
Escreva a contagem gulosa para um limite L: comece com um estudante e uma carga de 0; quando load + pages[i] > L, adicione um estudante e defina a carga como pages[i]; caso contrário, adicione o livro à carga.
Defina L como o livro mais espesso.
Enquanto a contagem para L for maior que students, adicione 1 a L.
Retorne L.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

Busca binária no limite da página

Intuição

A contagem gulosa é o menor número de estudantes que qualquer distribuição sob L pode usar. Comparado estudante por estudante com qualquer outra distribuição, cada estudante na distribuição gulosa só para quando o próximo livro não cabe, então termina pelo menos tão adiante na sequência de livros. Ter menos estudantes do que você tem é aceitável: um estudante com dois livros pode passar um para um estudante sem nenhum, e nenhuma carga aumenta.

Assim, L funciona exatamente quando a contagem gulosa é menor ou igual a students. Tudo o que funciona com L também funciona com L+1, então a busca binária encontra o primeiro limite que funciona.

O intervalo começa no maior valor entre max(pages) e a média por estudante, total / students arredondada para cima, já que a carga mais pesada é pelo menos igual a ambos. O limite superior é total. No primeiro exemplo, isso vai de 54 a 160, e a busca testa 107, 80, 67, 60, 64, 66 e 65.

Algoritmo

Se students > pages.length, retorne -1.
Some total e encontre o livro mais grosso. Defina lo como o maior entre o livro mais grosso e (total + students - 1) / students, e hi = total.
Enquanto lo < hi, calcule mid = lo + (hi - lo) / 2.
Execute a contagem gulosa para mid. Se for no máximo students, defina hi = mid; caso contrário, defina lo = mid + 1.
Retorne lo.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

Armadilhas e casos extremos

Ignorar a verificação de -1. Para [10, 20] e 3 estudantes, a contagem gulosa com limite de 20 é 2, então a busca retorna 20.
Começar o intervalo apenas pela média da divisão. Para [1, 9] e 2 estudantes, a média é 5 e, nesse caso, o algoritmo guloso deixa o livro de 9 páginas sozinho, conta 2 e retorna 5.
Testar se o valor é exatamente students. Para [5, 5, 5, 5, 5, 5] e 4 estudantes, a resposta é 10, quando a contagem gulosa é 3.
Ordenar os livros. [10, 1, 1, 10] com 2 estudantes resulta em 11, mas, ordenado como [1, 1, 10, 10], resulta em 12.

Perguntas frequentes3

O Problema de Alocação de Livros é o mesmo que a Soma Máxima de um Array Dividido?

Sim. Ambos dividem um array em um número fixo de blocos contíguos não vazios e minimizam a maior soma de bloco, e a mesma busca binária com a mesma verificação gulosa resolve ambos. A versão do livro adiciona o caso -1.

Qual é a complexidade de tempo do Problema de Alocação de Livros?

Tempo O(n log S) e espaço extra O(1), em que n é o número de livros e S é o total de páginas. Cada limite testado custa uma passagem pelos livros, e a busca testa cerca de log2 S limites: 29 em uma estante com 5 × 10^8 páginas.

Quando é impossível alocar os livros?

Somente quando houver mais alunos do que livros, pois cada aluno precisa de pelo menos um livro. Com livros suficientes, qualquer bloco de dois ou mais livros pode dar seu último livro a um aluno que não tenha nenhum, até que todos tenham um.

def allocateBooks(pages, students):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

pages = [25, 40, 15, 30, 50]
students = 3

Saída Esperada