Carrots for Rabbits

Si tienes una zanahoria y sabes en cuántos trozos quieres cortarla, ¿cómo la cortarías para minimizar el tiempo de comer de todos los segmentos de esa zanahoria?

Calcula el tiempo de comer cuando una zanahoria se corta en $1$, $2$, $3$ y más veces. ¿Qué observas sobre estos tiempos?

En la pista $2$, ¿qué observas sobre el cambio de esos tiempos a medida que aumenta el número de cortes?

Explicación

La suma de los cuadrados de dos números dada una suma fija se minimiza cuando los dos números son iguales. Si extendemos esa idea a cada zanahoria, entonces deben cortarse en trozos de longitudes lo más cercanas posible, sin que ningún par de longitudes difiera en más de $1$. En concreto, si una zanahoria de longitud $l$ se corta en $t$ partes, habrá $t-l\bmod t$ trozos de longitud $\lfloor\frac lt\rfloor$, y $l\bmod t$ trozos de longitud $\lfloor\frac lt\rfloor+1$. Sea $f(l,p)$ el tiempo que toma comer estos trozos, que se puede calcular en tiempo $\mathcal O(1)$.

Ahora, el problema se reduce a decidir el número de cortes de cada zanahoria. Intuitivamente, cuantos más trozos cortemos de una zanahoria, menor será el tiempo total. Y si calculamos a mano el tiempo para cada número de cortes, vemos que la disminución del tiempo tras cada corte también se vuelve más pequeña.

Para ver por qué, supongamos que los cortes son perfectamente parejos, permitiendo longitudes fraccionarias. En ese caso, $f(l, t)\approx t(\frac lt)^2=\frac{l^2}t$. Como la función es de la forma $g(x)=\frac ax$, $f$ decrece y lo hace cada vez más lento a medida que $t$ aumenta. Esto significa que al incrementar el número de cortes de una zanahoria, cada incremento ahorrará tiempo, pero el ahorro disminuirá a medida que avancemos.

Esto inspira una solución voraz, en la que fijamos que las zanahorias se corten inicialmente en $1$ segmento (sin cortar), y precomputamos la disminución de tiempo de esa zanahoria si el número de cortes se incrementa en $1$. Mantenemos una cola de prioridad de zanahorias ordenada por la disminución de tiempo descrita arriba; durante $k-n$ veces, tomamos la zanahoria con el mayor valor de cambio e incrementamos su número de cortes en $1$. Luego recomputamos el tiempo de comer esa zanahoria, y el cambio de ese tiempo si el número de cortes se incrementa aún más en $1$, antes de volver a colocar la zanahoria en la cola de prioridad.

Como los retornos son decrecientes para cada aumento de cortes, no puede haber una situación en la que elegir primero un corte subóptimo resulte en mejores cortes después para una zanahoria.

Implementación

Complejidad temporal: $\mathcal{O}(k\log n)$

#include <array>
#include <iostream>
#include <queue>
using namespace std;
 
int main() {
	int n, k;
	cin >> n >> k;
 
	// La cola de prioridad para el seguimiento.
	// Los elementos son de la forma {diff, length, cuts},
	// donde diff es la diferencia de tiempo si cuts se incrementa en 1.
	priority_queue<array<long long, 3>> carrots;
 
	// Calcular el costo dada la longitud de la zanahoria y el número de cortes.
	auto cost = [&](int length, int cuts) -> long long {
		long long avg = length / cuts;
		return 1ll * avg * avg * (cuts - length % cuts) +
		       1ll * (avg + 1) * (avg + 1) * (length % cuts);
	};
 
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		ans += 1ll * a * a;
		carrots.push({cost(a, 1) - cost(a, 2), a, 1});
	}
 
	for (int i = 0; i < k - n; i++) {
		auto [diff, length, cuts] = carrots.top();
		carrots.pop();
		ans -= diff;
		carrots.push(
		    {cost(length, cuts + 1) - cost(length, cuts + 2), length, cuts + 1});
	}
 
	cout << ans << '\n';
}