Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2433
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2433
Vende-se
Por OBI - Olimpíada Brasileira de Informática 2013 
Brazil
Timelimit: 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 (3 ≤ N ≤ 105) e K (N - K ≥ 2), indicando, respectivamente, quantos prédios a OBI possui, e quantos prédios ela pretende vender. A linha seguinte contém N inteiros Xi (1 ≤ Xi ≤ 106) onde todos os Xi são distintos, 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.
| Exemplos de Entrada | Exemplos de Saída |
|
5 2 10 7 4 8 2 |
3 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAX 100010
#define LIM 2147483647
int vetor[MAX], n, k, i, resposta = LIM;
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &vetor[i]);
sort(vetor, vetor + n);
for (int i = 0; i < = k; i++)
if (vetor[i + (n - k) - 1] - vetor[i] < resposta)
resposta = vetor[i + (n - k) - 1] - vetor[i];
printf("%d\n", resposta);
return 0;
}
Input
10 7 4 8 2
Output