Minimizing Difference

Análisis oficial 

Explicación

En lugar de intentar construir directamente el arreglo final, fijamos la diferencia máxima $d$ y comprobamos si es alcanzable en menos de $k$ operaciones. Si todos los elementos se pueden mover a algún intervalo de longitud $d$, entonces es claro que todos los valores mayores de $d$ también funcionan. Por lo tanto, la condición es monótona y podemos hacer búsqueda binaria sobre $d$.

Para que un arreglo tenga diferencia máxima $d$, todos los elementos deben estar en el rango $[L, L + d]$, donde $L$ es cualquier entero. Esto significa que nuestras operaciones deben mover los valores $a_i < L$ al rango incrementándolos hasta $L$, y tratar de forma similar los valores donde $a_i > L + d$.

Si conocemos $L$, podemos calcular rápidamente el número de operaciones necesarias para encajar todos los elementos en el rango $[L, L + d]$ usando sumas de prefijos y búsqueda binaria, lo cual detallaremos más adelante.

Elegir L

La intuición indica que fijar $L$ o $L+d$ a algún valor de $a_i$ es óptimo. Esto es cierto, y podemos justificarlo de forma informal estableciendo un paralelo con el problema de minimizar sumas, que se explora en CPH 6.4 . Una explicación más detallada está en el spoiler de abajo.

Calcular la respuesta final

Sabiendo que $L$ o $L+d$ debe coincidir con algún valor de $a_i$, podemos iterar sobre cada $a_i$ e intentar calcular el costo asociado a fijarlo como valor de $L$ o $L+d$.

Para un rango $[L, R]$, donde $R=L+d$, el costo de encajar todos los elementos en el rango es:

En otras palabras, sumamos los costos de mover los valores $a_i < L$ hasta igualar $L$, y los costos de mover los valores $a_i > R$ hasta igualar $R$.

Si ordenamos nuestro arreglo $a_i$, entonces un prefijo y un sufijo de valores tendrán que moverse para quedar dentro del rango. Usamos búsqueda binaria para hallar el prefijo y el sufijo de valores que hay que ajustar, y sumas de prefijos para sumar los valores relevantes de $a_i$.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N \log A)$, donde $A$ es el valor máximo de $a_i$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	ll k;
	cin >> n >> k;
 
	vector<int> a(n);
	for (int &x : a) cin >> x;
	sort(a.begin(), a.end());
 
	// calcular sumas de prefijos, usando indexación desde 1 por comodidad
	vector<ll> pref(n + 1);
	for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + a[i]; }
 
	auto check = [&](int d) -> bool {
		for (int i = 0; i < n; ++i) {
			// Caso 1: l = a[i] (extremo izquierdo fijado a a[i])
			{
				int l = a[i], r = l + d;
 
				// usar sumas de prefijos para calcular l - a_i para todo a_i < l
				ll cost_l = 1ll * i * l - pref[i];
 
				// usar sumas de prefijos para calcular a_i - r para todo a_i > r
				// usamos upper bound para hallar el primer índice desde el que sumamos
				int p = upper_bound(a.begin(), a.end(), r) - a.begin();
				ll cost_r = (pref[n] - pref[p]) - 1ll * (n - p) * r;
 
				if (cost_l + cost_r <= k) return true;
			}
 
			// Caso 2: l = a[i] - d (extremo derecho fijado a a[i])
			{
				int r = a[i], l = r - d;
 
				// usar sumas de prefijos para calcular a_i - r para todo a_i > r
				ll cost_r = (pref[n] - pref[i + 1]) - 1ll * (n - i - 1) * r;
 
				// usar sumas de prefijos para calcular l - a_i para todo a_i < l
				// usamos lower bound para hallar el último índice desde el que sumamos
				int p = lower_bound(a.begin(), a.end(), l) - a.begin();
				ll cost_l = 1ll * p * l - pref[p];
 
				if (cost_l + cost_r <= k) return true;
			}
		}
 
		return false;
	};
 
	int lo = 0, hi = a[n - 1] - a[0];
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
 
	cout << lo << '\n';
}