Considere o seguinte problema retirado sessão de prática da
Internacional Olympiad in Informatics 2007 em Zagreb na Croácia.
O problema a seguir é um ótimo exemplo da aplicação da busca
binária.
PEIXES
Em um pequeno país costeiro,
todas as cidades estão situadas em uma longa faixa costeira (que vai ser
modelada como uma linha reta). Uma estrada longa corre ao longo da costa, que
liga as cidades. A posição de cada cidade pode ser descrita por um número
inteiro não negativo único representando a distância (em km) a partir do início
da estrada. A maioria dos cidadãos são pescadores, e eles pegam grandes
quantidades de peixe. Após a temporada de pesca terminar e antes da alta
temporada começar, os peixes podem ser transportados entre diferentes cidades.
Uma cidade pode acomodar X turistas se tem toneladas de peixes X disponíveis. O
objetivo é para acomodar o maior número possível de turistas igualmente em cada cidade. Em outras
palavras, queremos encontrar o maior número inteiro Y para o qual é possível
distribuir os peixes de modo a que cada cidade pode acomodar, pelo menos, Y
turistas. Em uma transferência, um número inteiro de toneladas de peixes é
enviado de uma cidade para outra. Durante o transporte, uma tonelada de peixe
por quilômetro percorrido é perdido para saqueadores famintos que descem das
montanhas. Mais formalmente, se a navios cidade F toneladas de peixe para outra
cidade que é D quilômetros de distância, em seguida, toneladas FD vai chegar o
destino, se F é inferior a D, então, toda a carga é perdida. É possível
arbitrariamente reembalar e combinar envios em cidades intermediárias. Por
exemplo, podemos enviar embarques de cidades A e B para a cidade C, combinar a metade
do peixe restante de ambos os embarques com os peixes originários em C e
enviá-lo em uma única remessa grande de cidade C para a cidade D.
TAREFA
Escreva um programa que, dadas as
posições de todas as cidades e da quantidade de peixe de cada cidade produz, determina
o maior número de turistas que podem ser acomodados em cada cidade depois que o
peixe foi distribuído.
A primeira linha da entrada
contém um inteiro N, 1 ≤ N ≤ 100 000, o número de cidades.
ENTRADA
Cada uma das N linhas seguintes
contém dois inteiros P e F, 0 ≤ P, F ≤ 1012, a posição de uma cidade (em km) e
da quantidade de peixe que produz (em toneladas). As cidades serão
classificadas em ordem crescente de posição.
As posições de todas as cidades
sejam distintas.
SAÍDA
A primeira linha de saída e
apenas deve conter a maior quantidade de turistas Y a partir da descrição de
tarefas.
Entrada
3
1 0
2
21
4 0
Saída
6
|
input
3
5
70
15
100
1200
20
output
20
|
input
4
20
300
40
400
340
700
360
600
output
415
|
Primeiramente, precisamos fazer
algumas observações
- Um algoritmo guloso pode ser usado para descobrir se é possível acomodar X turistas em cada cidade. Podemos considerar as cidades da esquerda para a direita. Se uma cidade tem mais X unidades de peixes, então ela pode enviar o excedente para a cidade da direita. Se a cidade tem menos que X unidades, ela deve receber o que falta da cidade da esquerda.
- 1. Se um valor de turista X é possível então X-1 também é um valor possível. Por outro lado, se X não é possível então X+1 também não é possível. Logo, podemos usar uma busca binária para encontrar o maior valor X possível. A complexidade do algoritmo será O(N LG MAX), onde MAX é um limite superior para a solução do problema. Um bom limite superior seria a soma de toda produção de peixes divididos pelo número de cidades.
Nenhum comentário:
Postar um comentário