Medio · voraz
Tiempo mínimo de espera
El primero no hace esperar a nadie; el último hace esperar a todos. Cada minuto del llenado de alguien lo pagan los que van detrás — así que la cola más barata pone los tiempos pequeños donde se multiplican menos.
En una fraseOrdena en ascendente y acumula: la persona i espera la suma de todos los anteriores. Tras ordenar, <code>total += wait; wait += a[i]</code> es toda la solución.
El problema
Entrada: La primera línea es n (1 ≤ n ≤ 100). La segunda trae n enteros (1 ≤ a ≤ 1000): los segundos que tarda cada persona en llenar.
Salida: El tiempo total de espera mínimo posible, donde el tiempo de espera de alguien es todo lo anterior a que empiece su llenado (su propio llenado no cuenta).
Ejemplos:
| Entrada | Salida |
|---|---|
4 | 8 |
1 | 0 |
En el ejemplo, el mejor orden es 1, 1, 3, 4: esperan 0, 1, 2 y 5 — total 8. Cualquier otro orden paga más; se puede demostrar que el ordenado es el mínimo.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Escribe lo que cambia un intercambio
Toma dos vecinos x delante de y e imagina intercambiarlos. Solo cambian sus dos esperas: con x delante pagan y; con y delante pagan x. Intercambiar conviene justo cuando y < x — así que en una cola óptima toda pareja vecina es ascendente, lo que fuerza a la cola entera a estar ordenada. Ese es el argumento de intercambio, y es como demuestras un voraz en vez de esperar que funcione.
Pista 2 — El barrido es un prefijo corriente
Tras ordenar, la persona i espera la suma de a[0..i-1]. En vez de un bucle interno, lleva wait: por cada persona, total += wait; y después wait += a[i];. Dos sumas por persona, sin segundo bucle — la misma idea de prefijo que Sumas por rangos.
Pista 3 — La espera va antes, no después
El enunciado dice que el propio llenado no cuenta como espera. El barrido con prefijo lo hace bien de serie — pero si incluyes a[i] en el prefijo, toda respuesta sale agrandada en Σa[i], y el bug se esconde dentro de un número que parece plausible.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) {
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}Este es el principio de primero-el-trabajo-más-corto de los sistemas operativos, demostrado con cuatro líneas de argumento de intercambio. Su hermano ya lo conociste: Monedas mínimas era voraz con otra prueba, y Ordenamiento burbuja es la maquinaria que ambos reutilizan. Cuando un voraz te parezca correcto, el ejercicio es siempre el mismo: encuentra el intercambio que mejoraría cualquier respuesta no ordenada.
Análisis profundo
Por qué funciona
Argumento de intercambio: toma cualquier cola que no esté ordenada en ascendente e intercambia una pareja vecina desordenada (x delante de y con y < x). Solo cambian las esperas de esos dos, y bajan en x − y. Así que una cola desordenada siempre puede mejorarse, y el único óptimo local es el ordenado — eso es una demostración, no una esperanza.
El coste
O(n²) para la burbuja y O(n) para el barrido; con n ≤ 100 son unas 10.000 comparaciones. La espera total cabe de sobra en 64 bits (100 personas × 1000 s ≈ 5 millones de segundos).
Dónde falla
- Contar el propio llenado de cada persona como espera infla todas las respuestas en Σa[i] — el barrido debe hacer
total += waitANTES de ampliar wait con a[i]. - Ordenar una copia y barrer el array original (o al revés) — la respuesta en silencio no corresponde a ningún orden.
- Olvidar que los tiempos iguales pueden ir en cualquier orden entre sí: los empates son gratis, no compliques el orden por ellos.
Siguiente paso
La hermana voraz con otra prueba es Monedas mínimas — lee los dos argumentos de intercambio juntos. El ordenamiento que ambos reutilizan es Ordenamiento burbuja.
Dos cosas para recordar
- Primero los rápidos: cada minuto del que va delante lo pagan todos los de detrás.
- Argumento de intercambio = la plantilla de prueba del voraz: encuentra el intercambio que mejoraría cualquier respuesta desordenada.
🐞 Esta versión falla: ábrela y pruébala
Barre en orden de llegada: la cola nunca se ordenó
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) { // bug: no sorting first
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}