Aggressive Cows

Q: Qual é a complexidade de tempo de Aggressive Cows?

A ordenação leva O(n log n) e a busca binária, O(n log D) , onde D é a extensão dos estábulos dividida por k-1 . Além de uma cópia ordenada, o uso de memória é O(1) .

Q: Por que a primeira vaca sempre vai para o estábulo mais à esquerda?

Escolha qualquer posicionamento que funcione e mova sua vaca mais à esquerda para o estábulo mais à esquerda. Essa vaca só se afasta das outras, então nenhuma distância diminui, e algum posicionamento ótimo usa o estábulo mais à esquerda.

Q: Como identificar uma busca binária na resposta?

A pergunta pede o maior ou o menor valor para o qual algo é possível; verificar um valor é muito mais fácil do que encontrar o melhor, e as respostas mudam apenas uma vez à medida que o valor aumenta. Aqui, o valor é o intervalo e a verificação é o posicionamento guloso.

MédioBusca binária Ordenação Guloso

+10

Um celeiro tem baias ao longo de uma linha reta, e stalls[i] é a posição da baia i. Todas as posições são diferentes e não estão em nenhuma ordem específica. Você deve colocar k vacas em k baias diferentes, e as vacas brigam quando ficam perto umas das outras, então você quer que as duas vacas mais próximas fiquem o mais distantes possível.

Retorne o maior valor possível da menor distância entre quaisquer duas vacas.

Função

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: as posições distintas dos obstáculos, em qualquer ordem
kinteger: o número de vacas a colocar
Retornainteger: a maior menor distância possível entre duas vacas

Restrições

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Todas as posições em stalls são distintas.
2 ≤ k ≤ stalls.length

Exemplos

Entrada: stalls = [10, 1, 7, 4, 15]k = 3
Saída: 6
Explicação: As vacas nas posições 1, 7 e 15 ficam a 6 e 8 de distância. Uma distância de 7 não funciona: depois da posição 1, a próxima vaca vai para a posição 10, e não há nenhum estábulo na posição 17 ou além.

Para ir além

O que muda se as barracas estiverem dispostas em um círculo, de modo que a última barraca na sequência também seja vizinha da primeira?

Dicas

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

0 de 3 abertas

Solução

Defina uma distância e pergunte: é possível colocar k vacas de modo que cada par fique separado por pelo menos essa distância? Uma passagem gulosa pelas baias ordenadas responde a isso. A resposta muda de sim para não uma única vez conforme a distância aumenta, então a busca binária encontra o último sim.

Ordene e, em seguida, experimente cada lacuna por vez

Correta, mas não termina nos maiores testes

Intuição

Ordene as posições. As duas vacas mais próximas são sempre vizinhas, então uma distância g funciona quando cada par de vacas vizinhas está separado por pelo menos g.

Para testar uma distância, coloque uma vaca no estábulo mais à esquerda e, em seguida, uma em cada estábulo que esteja a pelo menos g do último ocupado por uma vaca. Essa colocação gulosa acomoda o maior número de vacas possível. Alinhe qualquer colocação válida pela esquerda: a vaca i da colocação gulosa nunca fica à direita da vaca i dessa outra colocação, então a estratégia gulosa encontra um estábulo para a próxima vaca não mais tarde.

Uma distância de 1 sempre funciona, então teste g = 2, 3, ... e pare na primeira distância que acomode menos de k vacas. No primeiro exemplo, a distância 6 acomoda 3 vacas e a distância 7, apenas 2, então a resposta é 6.

Com duas vacas e estábulos nas posições 0 e 10^9, isso representa cerca de 10^9 passagens por 5000 estábulos, ou 5 × 10^12 etapas.

Algoritmo

Ordene as posições.
Escreva a verificação para uma distância g: uma vaca em pos[0] e, em seguida, uma vaca em cada baia onde pos[i] - last ≥ g, contando as vacas.
Comece com gap = 1.
Enquanto a verificação de gap + 1 posicionar pelo menos k vacas, adicione 1 a gap.
Retorne gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Busca binária no intervalo

Intuição

Uma disposição com todos os intervalos de pelo menos g+1 também tem todos os intervalos de pelo menos g, então as verificações são sim, ..., sim, não, ..., não. A busca binária encontra o último sim.

Pesquise a partir de lo = 1, que sempre funciona, até hi = o comprimento dividido por k-1, arredondado para baixo: k vacas deixam k-1 intervalos dentro do comprimento, então a menor distância não pode ser maior. Uma verificação aprovada define lo = mid, então mid precisa ser arredondado para cima; arredondando para baixo, lo = 5 e hi = 6 se repetem para sempre.

No primeiro exemplo, o comprimento é 14 e k = 3, então hi = 7. O intervalo 4 é aprovado, o intervalo 6 é aprovado, o intervalo 7 falha, e o intervalo se fecha em 6.

Um intervalo de até 10^9 de largura se fecha em cerca de 30 verificações de 5000 baias, aproximadamente 150.000 etapas.

Algoritmo

Ordene as posições.
Defina lo = 1 e hi = (pos[n-1] - pos[0]) / (k-1), arredondado para baixo.
Enquanto lo < hi, calcule mid = lo + (hi - lo + 1) / 2.
Se a verificação gulosa em mid posicionar pelo menos k vacas, defina lo = mid; caso contrário, defina hi = mid - 1.
Retorne lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Armadilhas e casos extremos

Ignorar a ordenação. Na lista não ordenada [10, 1, 7, 4, 15] com intervalo 6, a verificação começa em 10, não encontra nenhum estábulo posterior que esteja a pelo menos 6 de distância e informa que há uma vaca.
Arredondar mid para baixo enquanto uma passagem define lo = mid. Quando hi = lo + 1, o intervalo para de diminuir e o loop nunca termina.
Testar se há exatamente k vacas. Com intervalo 1, o primeiro exemplo posiciona 5 vacas, mais do que 3, mas o intervalo funciona; teste count ≥ k.
Começar a contagem de vacas em 0. A vaca no estábulo mais à esquerda conta, então a contagem começa em 1.

Perguntas frequentes3

Qual é a complexidade de tempo de Aggressive Cows?

A ordenação leva O(n log n) e a busca binária, O(n log D), onde D é a extensão dos estábulos dividida por k-1. Além de uma cópia ordenada, o uso de memória é O(1).

Por que a primeira vaca sempre vai para o estábulo mais à esquerda?

Escolha qualquer posicionamento que funcione e mova sua vaca mais à esquerda para o estábulo mais à esquerda. Essa vaca só se afasta das outras, então nenhuma distância diminui, e algum posicionamento ótimo usa o estábulo mais à esquerda.

Como identificar uma busca binária na resposta?

A pergunta pede o maior ou o menor valor para o qual algo é possível; verificar um valor é muito mais fácil do que encontrar o melhor, e as respostas mudam apenas uma vez à medida que o valor aumenta. Aqui, o valor é o intervalo e a verificação é o posicionamento guloso.

def aggressiveCows(stalls, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

stalls = [10, 1, 7, 4, 15]
k = 3

Saída Esperada