0

Verán, he estado aprendiendo y practicando programación competitiva, y en un problema de un concurso tenía que hacer una búsqueda en un arreglo bidireccional. Hice lo primero que pensé, una búsqueda anidada y contadores pero solo obtuve el 75% correcto de los casos. Cuando dieron las soluciones, en ese problema solo mencionaron que se usa una estructura de datos de la cual no supe descifrar el hombre porque es muy raro, recuerdo escuchar "monotonons jack". Quisiera ver si alguien me pudiera decir si existe esta estructura de datos o una parecida.

Aquí el código que hice (en java) y las indicaciones del problema: Limite de Memoria: 32MiB Limite de tiempo por caso: 500 ms Limite de tiempo total: 1 min

Entrada

Un entero N seguido de las N alturas de los edificios. Puedes suponer que 0≤N≤1050≤N≤105 y que las alturas de los edificios son distintas y en el rango de 11 a 109109.

Salida

Para cada edificio, la cantidad de azoteas que puedes ver desde ahí.

Ejemplo

Entrada

6

7 1 4 3 5 2

Salida

6 1 3 1 5 1

codigo

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class edificio {

    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int veces = Integer.parseInt(br.readLine());
            String cad = br.readLine();
            StringTokenizer st = new StringTokenizer(cad, " ");
            ArrayList<Integer> v1 = new ArrayList<>();
            ArrayList<Integer> v2 = new ArrayList<>();
            for (int i = 0; i < veces; i++) {
                v1.add(Integer.parseInt(st.nextToken()));
            }
            int cont = 0, cont2;
            for (int i = 0; i < v1.size(); i++) {
                for (int j = i; j < v1.size(); j++) {
                    if (v1.get(i) >= v1.get(j)) {
                        cont++;
                    } else {
                        break;
                    }
                }
                cont2 = cont;
                cont = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (j >= 0 && j <= v1.size()) {
                        if (v1.get(i) > v1.get(j)) {
                            cont2++;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                v2.add(cont2);
            }
            System.out.println(v2);
        } catch (Exception e) {
        }
    }

}
1
  • No se entiende esa consigna. ¿Qué es lo que pide en el programa? Si dieras más detalles, sería de gran ayuda.
    – MrDave1999
    Commented el 16 may. 2020 a las 16:19

1 respuesta 1

0

Primer número: Dimensión para Array1 y Array2.

Array1: Altura de edificios.

Array2: Azoteas visibles desde cada edificio de Array1.

(Desconozco si un array de 2 dimensiones sería más efectivo que 2 arrays de 1)

Recorre cada posición del array 1 y para cada posición, la comparas con las demás. Y cuentas según si quieres que sean igual o menor, o sólo menor. Y usas un contador. Cuando acabes la comparación de la primera posición con las demás, metes el contador en esa posición, pero del Array2.

En estos concursos no sólo se mide la capacidad lógica y mental de resolución de problemas, sino el conocimiento del lenguaje. Y en este caso hay varios datos a tener en cuenta:

  • Cómo hace ArrayList para redimensionar su tamaño con la adición de elementos.
  • Qué pasa con las dimensiones iniciales no utilizadas en un ArrayList.
  • Un Array es en la mayoría de situaciones más efectivo que un ArrayList, sólo que es más incómodo por su rigidez de tamaño.
  • Un bucle for each es más efectivo que un un bucle for normal en muchas más situaciones.
  • Un operador ternario es más rápido que un if. Sólo que un if puede tener más de 2 alternativas (más que un true-false, ya que puede enlazarse con muchos else if y cada uno de ellos con una condición que puede no tener nada que ver con la condición anterior). Pero si sólo se mide 1 condición con sus posibles resultados true o false para esa única solución, el operador ternario es más rápido en su ejecución que el condicional if.

Por último, si sales de este ejemplo concreto y te vas a otros, probablemente necesites saber más sobre las clases no esenciales de java (las que se enseñan en un curso normal) al igual que otros conceptos sobre el funcionamiento interno de java.

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.