equality.cpp

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