0

Entrada John Carter está huyendo a caballo de los indios de Arizona. Adelante de él ve el horizonte lleno de cactus. Rápidamente se aprende sus posiciones y voltea a ver a los indios que lo persiguen, pensando en algunas posiciones en el horizonte a las cuales dirigir su caballo para escapar. Ayuda a John Carter a saber cuánto espacio tiene para pasar entre los cactus para cada posición que esté considerando.

Entrada Un entero N seguido de las posiciones C1, ......, Cn de los cactus en el horizonte. Posteriormente, un entero M seguido de las posiciones P1, ......., Pm consideradas. Puedes suponer que 2≤N, M≤10,000, que todas las posiciones están en el rango de -100,000 a 100,000 y que minCi≤Pj≤maxCi para toda 1≤j≤M.

Salida M enteros D1, ......, Dm, donde Dj es la distancia entre los dos cactus que pasará John Carter en la posición Pj (o 0 si John Carter se estrellará con un cactus).

El problema persiste en que la salida que obtengo no es la esperada, ya implemente una búsqueda binaria, iterando sobre las posiciones para poder encontrarlas, pero no se que me falla.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    vector<int> cactus(n);
    for (int i = 0; i < n; ++i) {
        cin >> cactus[i];
    }

    cin >> m;
    vector<int> posiciones(m);
    for (int i = 0; i < m; ++i) {
        cin >> posiciones[i];
    }

    // Iteramos sobre las posiciones consideradas
    for (int j = 0; j < m; ++j) {
        int posicion = posiciones[j];

        // Inicializamos la distancia mínima como infinito
        int distancia_minima = INT_MAX;

        // Buscamos la distancia mínima a cada cactus
        for (int k = 0; k < n; ++k) {
            int distancia = abs(posicion - cactus[k]);
            if (distancia < distancia_minima) {
                distancia_minima = distancia;
            }
        }

        // Imprimir la distancia mínima
        cout << distancia_minima << " ";
    }
    cout << endl;

    return 0;
}

Mi salida es:

1 2 0 1

Cuando debería ser:

introducir la descripción de la imagen aquí

1
  • Estas calculando la distancia entre el punto Pj y el más cercano de los dos cactus a ese punto, mientras lo que parece que pide el problema es la distancia de esos dos cactus entre ellos
    – Juan_m_2
    Commented el 23 mar. a las 23:14

2 respuestas 2

1

Yo también opté por ordenar el vector como @Mateo, pero con una implementación del bucle principal un poco diferente. La incluyo en caso de que pueda ser útil.

  for (int j = 0; j < m; ++j) {
    int posicion = posiciones[j];

    if (posicion < cactus[0] || posicion > cactus[n -1]) continue;
    for (int k = 0; k < n; ++k) {
      if (posicion <= cactus [k]) {
        if (posicion == cactus[k]) cout << "0 ";
        else cout << cactus[k] - cactus[k - 1] << " ";
        break;
      }
    }
  }
1

Te falta un paso. Debes encontrar los 2 cactus entre los que pasa y obtener la distancia entre ellos.

Será más fácil si ordenas el vector. Ya que los 2 cactus entre los que pasa estarán juntos en el vector.

El código sería el siguiente:

// Agrega estos include
#include <algorithm>
#include <iterator>

int n, m;
cin >> n;
vector<int> cactus(n);
for (int i = 0; i < n; ++i) {
    cin >> cactus[i];
}
sort(cactus.begin(), cactus.end());

cin >> m;
vector<int> posiciones(m);
for (int i = 0; i < m; ++i) {
    cin >> posiciones[i];
}

// Iteramos sobre las posiciones consideradas
for (int i = 0; j < m; ++j) {
    int posicion = posiciones[i];

    auto cactus_posterior = find_if(cactus.begin(), cactus.end(), [=](int p){
        return p >= posicion;
    });
    auto cactus_anterior = prev(cactus_posterior);
    
    if (cactus_posterior == cactus.end() || cactus_posterior == cactus.begin()) {
        // Hacer lo que corresponda si no encuentra alguno de los cactus
    }

    int distancia = *cactus_posterior - *cactus_anterior;     

    // Si la distancia entre los cactus es 1, debe haber chocado uno
    if (distancia == 1) distancia = 0;

    // Imprimir la distancia mínima
    cout << distancia << " ";
}

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.