uCoder | 1059 | Nível: 4 | Tempo Limite: 10
Vende-se
Adaptado por Erich Rodrigues
Competição: OBI 2013, Nível 2, Fase 1
A Otacílio Busílis Imóveis (OBI) é a maior imobiliária de Nlogópolis, especializada no aluguel de prédios comerciais; todas as suas propriedades se localizam na Avenida Doutor Otacílio Busílis, assim chamada em homenagem ao fundador da OBI.
Devido à crise econômica mundial, a OBI precisa vender K de seus imóveis para levantar capital de giro. Dr. Otacílio quer que os prédios restantes após a venda sejam o mais próximos possível — ou seja, a distância entre o primeiro e o último prédios restantes deve ser a menor possível.
Infelizmente, a OBI é proprietária de tantos prédios que o Dr. Otacílio não sabe quais prédios ele deve vender; ele lhe contratou para que você escreva um programa que determina qual é a mínima distância possível entre o primeiro e o último prédios da OBI na avenida, após a venda de K prédios.
Entrada
A primeira linha da entrada contém os inteiros N e K, indicando, respectivamente, quantos prédios a OBI possui, e quantos prédios ela pretende vender. A linha seguinte contém N inteiros Xi , indicando a distância de cada um dos N prédios ao início da avenida, em metros.
Saída
A saída deve conter um único inteiro indicando a menor distância possível entre o primeiro e o último prédio
possuídos pela OBI após a venda.
Restrições
• 3 <= N <= 10^5
• N - K >= 2
• 1 <= Xi <= 10^6
• todos os Xi são distintos
Exemplo de Entrada | Exemplo de Saída |
---|---|
8 6 |
1 |
5 2 |
3 |