Solução Informática Intermediário - Semana 53 - Problema 2

Solução por Sofhia Souza

Se pararmos para analisar, veremos que não faz sentido retirarmos um valor $x_i$ que está entre outros dois valores, afinal, se fizermos isso, a diferença entre $x_{i-1}$ e $x_{i+1}$ será maior do que a diferença que existia entre $x_i$ e $x_{i-1}$ e entre $x_i$ e $x_{i+1}$ , pois o vetor é crescente. Logo, é possível enxergar que devemos retirar os valores somente das pontas, de maneira que o maior valor seja o menor possível. Para fazermos isso, nós primeiro calculamos o vetor dos valores das diferenças (afinal, são esses os valores que interessam), e depois percorremos esse vetor, calculando o maior valor de todos os intervalos possíveis (se meu intervalo é da posição $i$ até a posição $j$ , significa que retirei todos os $i-1$ primeiros valores e todos os $n-j$ valores seguintes, sendo $(i-1 + n-j) = k$ ).

Código para melhor entendimento:

	#include <bits/stdc++.h>
	#define inf 1000000000
	using namespace std;

	int main()
	{
	int n, k, vet[10010], dif[10010];

	cin >> n >> k;

	for(int i = 1 ; i <= n ; i++)
	{
	cin >> vet[i];
	if(i != 1) dif[i-1] = abs(vet[i]-vet[i-1]); //guardo o valor das diferenças no meu vetor dif
	}

	int resp = inf;

	for(int i = 1 ; i <= k ; i++)
	{
	int maior = 0;
	for(int j = i ; j < (n-k+i-1) ; j++) maior = max(maior, dif[j]); //percorro todos os intervalos possiveis e pego o maior de cada um
	resp = min(maior, resp); //pego o menor dos maiores
	}

	cout << resp << endl;
	}

view raw intermediario-53-2.cpp hosted with ❤ by GitHub