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; | |
| } |
Comente