Solução por Thiago Mota
Uma solução gulosa sempre diminui o maior número e incrementa o menor, enquanto necessário. A resposta pode ser muito grande, então simplesmente simular as operações não se encaixa no limite de tempo.
No entanto, podemos tentar melhorar essa ideia. Em vez de executar operação por operação, podemos construir um vetor de frequências 
que guarda o número de vezes que aquele número aparece, se 
for o menor valor e 
for o maior valor e 
, podemos aumentar 
valores 
e diminuir valores 
custando operações, com isso sempre diminuiremos o maior valor ou aumentaremos o menor.
Para isso podemos utilizar Two Pointers para o mínimo e para o máximo, e sair mudando a frequência dos valores, a complexidade fica em 
sendo 
a diferença entre o maior e o menor valor, como os valores vão até 
, a complexidade passará no tempo da questão. Segue o código:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Solucao Informatica Avancado Semana 59 | |
| // Thiago Mota | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 100010; | |
| int f[maxn]; | |
| int n; | |
| int main() { | |
| int k; | |
| cin >> n >> k; | |
| int l=maxn, r=-1; // l = menor valor, r = maior valor | |
| for(int i=1;i<=n;i++) { | |
| int x; | |
| cin >> x; | |
| l = min(l, x); | |
| r = max(r, x); | |
| f[x]++; | |
| } | |
| int ans=0; | |
| // Two pointers | |
| while(true) { | |
| while(l < r && f[l] == 0) l++; // Se a frequencia de l for igual a 0 significa que o menor valor esta mais a direita. | |
| while(l < r && f[r] == 0) r--; // Mesma coisa aplicada ao r. | |
| if(r - l <= k) break; | |
| if(l >= r) break; | |
| // Agora l e r mantem respectivamente o menor e o maior valor. | |
| int c = min(f[l], f[r]); | |
| // Para aumentar l em 1, basta aumentar a frequencia de l+1 e diminuir de l | |
| f[l+1] += c; | |
| f[l] -= c; | |
| // Para diminuir r em 1, basta diminuir a frequencia de r e aumentar de r-1 | |
| f[r] -= c; | |
| f[r-1] += c; | |
| ans += c; // Aumenta o número de operacoes em c, pois fizemos isso para "c" ocorrencias de l e r | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |