0

Les brindaré información respecto al problema:

Descripción

Junto con tus amigos, acabas de organizar una salida al famoso parque de diversiones Six Flags. Su deseo es subirse a todos los juegos del parque, pero no contabas con que los juegos tienen un requisito de estatura mínima y con que varios de tus amigos son bastante chaparritos. Como eres muy solidario y no quieres excluir a nadie, acordaron que sólo se subirán a los juegos en los que todos cumplan el requisito de estatura. ¿A cuántos juegos podrán subirse?

Entrada

Inicialmente, dos enteros N y M. Posteriormente, una secuencia de N enteros que denotan los requisitos de estatura mínima de los N juegos del parque. Finalmente, una secuencia de M enteros que denotan las estaturas de tu grupo de amigos, incluyéndote. Puedes suponer que 1≤N,M≤10^5 y que todas las estaturas están en centímetros en el rango de 0 a 250.

Salida

Un entero que sea la cantidad de juegos a los que todos se pueden subir.

La cuestión es que OmegaUp me marca como respuesta demasiado lenta (TLE), traté de modificar vector con set, pero no obtuve el resultado esperado, ¿cómo podría optimizar esto para que el tiempo de respuesta sea más rápido?. Saludos.

Código:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Lectura de la cantidad de juegos (N) y de amigos (M)
    int N, M;
    cin >> N >> M;

    // Lectura de las estaturas mínimas requeridas para los juegos
    vector<int> estaturas_juegos(N);
    for (int i = 0; i < N; ++i) {
        cin >> estaturas_juegos[i];
    }
    
    // Lectura de las estaturas de los amigos
    vector<int> estaturas_amigos(M);
    for (int i = 0; i < M; ++i) {
        cin >> estaturas_amigos[i];
    }

    // Contador para los juegos a los que todos se pueden subir
    int juegos_subirse = 0;

    // Verificar para cada juego si todos los amigos pueden subirse
    for (int i = 0; i < N; ++i) {
        bool pueden_subirse = true;
        for (int j = 0; j < M; ++j) {
            if (estaturas_amigos[j] < estaturas_juegos[i]) {
                pueden_subirse = false;
                break;
            }
        }
        if (pueden_subirse) {
            juegos_subirse++;
        }
    }

    // Imprimir el número de juegos a los que todos pueden subirse
    cout << juegos_subirse << endl;

    return 0;
}

1 respuesta 1

2

Hay una forma más simple de ver el problema. Los juegos establecen una altura mínima, así que solo debes asegurarte que la persona más pequeña pueda entrar al juego. Ya que si él puede los demás también.

Entonces, mejor encuentra a la persona más baja y trabaja con eso. Así pasas de un for doble a uno solo.

for (int i = 0; i < N; ++i)
    if (estaturas_juegos[i] <= estatura_menor)
        juegos_subirse++;

Por otra parte, es una pérdida de tiempo guardar toda la información en este caso. Solo usas una sola vez cada dato, por lo tanto puedes eliminar los vectores e ir calculando sobre la marcha.

int estatura_menor = 0;
int estatura;
for (int i = 0; i < personas; ++i) {
    cin >> estatura;
    if (estatura < estatura_menor)
       estatura_menor = estatura;
}

for (int i = 0; i < juegos; ++i)
    cin >> estatura;
    if (estatura <= estatura_menor)
        juegos_subirse++;
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.