Consulta de Percentiles W38626

Disponemos de los datos de un ranking de jugadores, cada uno con su nombre (un string) y sus puntos (un int). La puntuación de todos los jugadores es única (no hay empates). Si los ordenamos por puntuación de mayor a menor, el percentil de un jugador es el porcentaje de jugadores que tiene por debajo (incluyéndose a sí mismo) en el ranking.

Por ejemplo, en el siguiente ranking se muestran el nombre, los puntos y el percentil de un grupo de 5 jugadores, ordenados por puntos descendentemente:

Haced un programa que lea las puntuaciones de un ranking de jugadores y después conteste una serie de consultas, en las que se pide un nombre y hay que contestar con el percentil del jugador pedido. El programa se debe diseñar teniendo en cuenta que el número de consultas es, típicamente, dos órdenes de magnitud mayor que el número de jugadores del ranking.

Observación

En este problema el centro de interés es la eficiencia. Se trata de aplicar los mejores algoritmos conocidos y encontrar formas de hacer el mínimo número de operaciones para poder producir la salida.

El uso del algoritmo sort de vector está permitido en este problema. Como recordatorio, para usar sort, haría falta:

• Añadir #include <algorithm>.

• Definir una función de comparación fcomp que reciba dos elementos constantes a y b y retorne true si a va antes que b en la ordenación final.

• Llamar a sort(v.begin(), v.end(), fcomp), suponiendo que v es el vector que se quiere ordenar.

Entrada

La entrada tiene dos partes. Primero hay una secuencia de nombres de jugadores, acabada en "---", donde cada jugador va acompañado de su puntuación. Las puntuaciones de todos los jugadores son diferentes, es decir, no hay jugadores empatados a puntos. El orden de los jugadores es arbitrario. Después sigue una secuencia sin centinela de nombres de jugadores de los cuales se quiere consultar el percentil.

Salida

La salida es simplemente el percentil de cada jugador consultado, uno por línea. Los percentiles hay que mostrarlos con 2 decimales. Para mostrar dos decimales con todos los números reales de un programa se suele poner, al principio de la función main:

cout.precision(2);
cout.setf(ios::fixed);