Problema 1

Este es un problema de prueba, sin detalles específicos.

Problema 2: K números más cercanos a la mediana

Dada una secuencia de enteros a1, a2, ..., an y una constante k, se debe encontrar la mediana m de la secuencia, junto con los k números más cercanos menores o iguales a m y los k números más cercanos mayores o iguales a m. Estos 2k+1 números deben ordenarse de forma ascendente y mostrarse como salida.

Definición de mediana: Si el tamaño de la sceuencia es par (2j), la mediana es el j-ésimo número en el ordenamiento. Si es impar (2j+1), la mediana es el (j+1)-ésimo número.

Entrada:

• La primera línea contiene el valor de k y la longitud n de la secuencia.
• La segunda línea contiene n enteros separados por espacios.

Salida:

Una línea con los 2k+1 números ordenados, separados por espacios. Puede haber números repetidos.

Enfoque de solución:

Ordenar toda la secuencia directamente puede causar un tiempo de ejecución excesivo. Se utiliza un método basado en la partición de quickselect para encontrar la mediana de manera eficiente, con una complejidad de O(n). Una vez localizada la mediana, el arreglo queda particionado en elementos menores, la mediana misma y elementos mayores. Dado que k es pequeño, se pueden seleccionar los k vecinos más cercanos en cada lado mediente búsquedas simples en los segmentos correspondientes.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// Encuentra el k-ésimo elemento (en orden) usando partición.
int ubicarElementoK(vector<int>& datos, int inicio, int fin, int posicionObjetivo) {
    int pivote = datos[fin];
    int i = inicio;
    for (int j = inicio; j < fin; j++) {
        if (datos[j] <= pivote) {
            swap(datos[i], datos[j]);
            i++;
        }
    }
    swap(datos[i], datos[fin]);

    if (i == posicionObjetivo) {
        return i;
    } else if (i < posicionObjetivo) {
        return ubicarElementoK(datos, i + 1, fin, posicionObjetivo);
    } else {
        return ubicarElementoK(datos, inicio, i - 1, posicionObjetivo);
    }
}

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

    // Encontrar el índice de la mediana
    int indiceMediana = ubicarElementoK(secuencia, 0, n - 1, (n - 1) / 2);

    // Buscar k elementos menores más grandes en el segmento izquierdo
    for (int contador = 0; contador < k; contador++) {
        int maxValor = INT_MIN;
        int posMax = -1;
        for (int i = 0; i < indiceMediana - contador; i++) {
            if (secuencia[i] > maxValor) {
                maxValor = secuencia[i];
                posMax = i;
            }
        }
        if (posMax != -1) {
            swap(secuencia[posMax], secuencia[indiceMediana - contador - 1]);
        }
    }

    // Buscar k elementos mayores más pequeños en el segmento derecho
    for (int contador = 0; contador < k; contador++) {
        int minValor = INT_MAX;
        int posMin = -1;
        for (int i = indiceMediana + contador + 1; i < n; i++) {
            if (secuencia[i] < minValor) {
                minValor = secuencia[i];
                posMin = i;
            }
        }
        if (posMin != -1) {
            swap(secuencia[posMin], secuencia[indiceMediana + contador + 1]);
        }
    }

    // Imprimir el resultado ordenado de la ventana
    int inicio = indiceMediana - k;
    int fin = indiceMediana + k;
    for (int i = inicio; i <= fin; i++) {
        cout << secuencia[i];
        if (i < fin) cout << " ";
    }
    cout << endl;

    return 0;
}

Descripción:

Dado un arreglo de enteros arr ordenado de forma ascendente y sin elementos duplicados, junto con un número objetivo c. Encontrar todos los pares de números (a, b) en arr tal que a + b = c.

Entrada:

• Primera línea: el número de elementos n.
• Segunda línea: los elementos de arr, separados por espacios.
• Tercera línea: el número objetivo c.

Salida:

Cada par que cumpla la condición se imprime en una línea como a b, donde a < b. Los pares se ordenan de forma ascendente según el valor de a.

Enfoque de solución:

Una solución directa es verificar todos los pares posibles. Dado que el arreglo está ordenado, se puede usar un enfoque de dos punteros para mejorar la eficiencia, pero la solución de fuerza bruta con complejidad O(n²) es suficiente para cumplir los requisitos del problema.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arreglo(n);
    for (int i = 0; i < n; i++) {
        cin >> arreglo[i];
    }
    int objetivo;
    cin >> objetivo;

    // Buscar todos los pares que suman el objetivo
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arreglo[i] + arreglo[j] == objetivo) {
                cout << arreglo[i] << " " << arreglo[j] << endl;
            }
            // Dado que el arreglo está ordenado, si la suma excede el objetivo, 
            // se puede romper el bucle interno para ahorrar tiempo.
            if (arreglo[i] + arreglo[j] > objetivo) {
                break;
            }
        }
    }

    return 0;
}