Pista 1

Si se selecciona un grupo de \(K\) ciclistas, la velocidad final a la que todos pueden ajustarse está limitada por el ciclista más lento dentro de ese grupo.

Pista 2

Para maximizar esta velocidad final, conviene elegir a los \(K\) ciclistas con mayores velocidades máximas.

Solución

Cada ciclista tiene una velocidad máxima que no puede exceder. Al elegir un grupo de \(K\) ciclistas y forzar que todos vayan a la misma velocidad, dicha velocidad será necesariamente el mínimo de las velocidades de ese grupo.

El objetivo es maximizar esa velocidad mínima.

Para lograrlo, se observa que la mejor elección consiste en seleccionar a los \(K\) ciclistas más rápidos, ya que cualquier otro grupo tendría un ciclista con velocidad menor o igual al de este conjunto.

Procedimiento

1. Leer las velocidades de los \(N\) ciclistas.
2. Ordenarlas de mayor a menor.
3. La respuesta será la velocidad del ciclista en la posición \(K - 1\), ya que este es el ciclista más lento entre los \(K\) más rápidos.

Esta velocidad es la mayor posible a la que los \(K\) ciclistas pueden igualarse sin que ninguno exceda su límite.

Implementación en C++

Peregrinos_en_Bicicleta_de_Ruta.cpp

Complejidad

• Tiempo: Ordenar las velocidades requiere \(O(N \log N)\).
• Memoria: Se utiliza \(O(N)\) para almacenar las velocidades.