Resumen de la prueba de búsqueda binaria del 17 de agosto

Enlace a la competición

Putnuación

A. Cortar árboles	B. Comprar madera	C. Segmentación de array II	D. Comer helados	E. Saltando piedras	F. Vacas secando ropa
100	80	100	\(_{No resuelto:(}\)	10	0

Puntuación total

\(_{Muy mal}\)

T1. P1873 [COCI 2011/2012 #5] EKO / Cortar árboles

Enlace al problema

Análisis del problema

Utilizar búsqueda binaria con una función de verificación

La función verificar se usa para comprobar si la solución es válida

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1000007;
int cantidadArboles, maderaRequerida;
vector<int> alturasArboles;
bool verificar(int alturaMinima)
{
    int maderaObtenida = 0;
    for (int i = 0; i < cantidadArboles; ++i)
    {
        if (alturasArboles[i] > alturaMinima)
        {
            maderaObtenida += (alturasArboles[i] - alturaMinima);
        }
    }
    return maderaObtenida >= maderaRequerida;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> cantidadArboles >> maderaRequerida;
    int maxAltura = 0;
    alturasArboles.resize(cantidadArboles);
    for (int i = 0; i < cantidadArboles; ++i)
    {
        cin >> alturasArboles[i];
        maxAltura = max(maxAltura, alturasArboles[i]);
    }
    int izquierda = 1, derecha = maxAltura + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            izquierda = medio;
        }
        else
        {
            derecha = medio;
        }
    }
    cout << izquierda << "\n";
    return 0;
}

T2. B3880 [Información y Futuro 2015] Comprar madera

Enlace al problema

Código Incorrecto:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
vector<int> longitudes, cantidades;
int numProveedores, maderaRequerida;
bool verificar(int longitudMinima)
{
    int totalMadera = 0;
    for (int i = 0; i < numProveedores; ++i)
    {
        totalMadera += longitudes[i] / longitudMinima * cantidades[i];
        if (totalMadera >= maderaRequerida)
        {
            return true;
        } 
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> numProveedores >> maderaRequerida >> longitudes[0] >> cantidades[0];
    int maxLongitud = INT_MIN;
    for (int i = 1; i < maderaRequerida; ++i)
    {
        longitudes[i] = ((longitudes[i-1] * 37011 + 10193) % 10000) + 1;
        cantidades[i] = ((cantidades[i-1] * 73011 + 24793) % 100) + 1;
        maxLongitud = max(longitudes[i], maxLongitud);
    }
    int izquierda = 0, derecha = maxLongitud + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            izquierda = medio;
        }
        else
        {
            derecha = medio;
        }
    }
    cout << izquierda << "\n";
    return 0;
}
/*
10 10000 8 20
*/

Análisis del problema

Mediante las dos fórmulas dadas en el problema:

\(l_i=((l_{i-1}\times37011+10193) \bmod 10000)+1\)

\(s_i=((s_{i-1}\times73011+24793) \bmod 100)+1\)

Y los valores iniciales proporcionados, calcular el tamaño de cada número subsiguiente

Utilizar búsqueda binaria con una función de verificación para encontrar la solución válida

Análisis del error

Los detalles determinan el éxito

El problema dice:

Una línea con cuatro enteros \(n,m,l_1,s_1\). Donde \(l_1\) es la longitud de la madera del primer proveedor y \(s_1\) es la cantidad de madera del primer proveedor.

¡Y mi entrada por qué era \(m\) !!! \(_{Me enoja mucho}\)

Código Acpetado:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
vector<int> longitudes, cantidades;
int numProveedores, maderaRequerida;
bool verificar(int longitudMinima)
{
    int totalMadera = 0;
    for (int i = 0; i < numProveedores; ++i)
    {
        totalMadera += longitudes[i] / longitudMinima * cantidades[i];
        if (totalMadera >= maderaRequerida)
        {
            return true;
        } 
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> numProveedores >> maderaRequerida >> longitudes[0] >> cantidades[0];
    int maxLongitud = INT_MIN;
    for (int i = 1; i < numProveedores; ++i)
    {
        longitudes[i] = ((longitudes[i-1] * 37011 + 10193) % 10000) + 1;
        cantidades[i] = ((cantidades[i-1] * 73011 + 24793) % 100) + 1;
        maxLongitud = max(longitudes[i], maxLongitud);
    }
    int izquierda = 0, derecha = maxLongitud + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            izquierda = medio;
        }
        else
        {
            derecha = medio;
        }
    }
    cout << izquierda << "\n";
    return 0;
}
/*
10 10000 8 20
*/

T3. P1182 Segmentación de array II

Enlace al problema

Problema previo P1181 Segmentación de array I

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
vector<int> elementos;
int n, m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int suma = 0, segmentos = 1;
    elementos.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> elementos[i];
        if (suma + elementos[i] <= m)
        {
            suma += elementos[i];
        }
        else
        {
            segmentos++;
            suma = elementos[i];
        }
    }
    cout << segmentos << "\n";                      
    return 0;
}

Volviendo al problema actual (P1182)

Usar la mayor parte del código de P1181 como la función verificar para P1182

El código específico es el siguiente:

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
int n, m;
vector<int> elementos;
bool verificar(int maximoSegmento)
{
    int contador = 1;
    int sumaActual = 0;
    for (int i = 0; i < n; ++i)
    {
        if (sumaActual + elementos[i] <= maximoSegmento)
        {
            sumaActual += elementos[i];
        }
        else
        {
            contador++;
            sumaActual = elementos[i];
        }
    }
    return contador <= m;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int sumaTotal = 0;
    int maxElemento = 0;
    elementos.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> elementos[i];
        maxElemento = max(maxElemento, elementos[i]);
        sumaTotal += elementos[i];
    }
    int izquierda = maxElemento - 1;
    int derecha = sumaTotal + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            derecha = medio;
        }
        else
        {
            izquierda = medio;
        }
    }
    cout << derecha << "\n";
    return 0;
}
/*
5 3
4 2 4 5 1
*/

T4. B3629 Comer helados

Enlace al problema

Código Incorrecto:

Análisis del problema

Al resolverlo, pensé en usar simulación + enumeración

El problema menciona búsqueda binaria

Pero no supe cómo aplicarla 😦

Cuantos más helados se compran, más palitos de helado quedan,

Más helados se canjearán y el total de helados aumentará

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
int nHelados;
bool verificar(int cantidadInicial)
{
    int totalHelados = cantidadInicial;
    int palitosRestantes = cantidadInicial;
    while (palitosRestantes >= 3)
    {
        int nuevosHelados = palitosRestantes / 3;
        palitosRestantes = palitosRestantes % 3;
        totalHelados += nuevosHelados;
        palitosRestantes += nuevosHelados;
    }
    return totalHelados >= nHelados;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> nHelados;
    int izquierda = 1 - 1;
    int derecha = nHelados + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            derecha = medio;
        }
        else
        {
            izquierda = medio;
        }
    }
    cout << derecha << "\n";
    return 0;
}

T5. P2678 [NOIP2015 Grupo avanzado] Saltando piedras

Enlace al problema

Código Incorrecto:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
vector<int> posicionesPiedras;
int longitudTotal, numPiedras, piedrasEliminar;
bool verificar(int distanciaMinima)
{
    int saltos = 1;
    int ultimaPosicion = 0;
    for (int i = 1; i <= numPiedras; ++i)
    {
        if (posicionesPiedras[i] - posicionesPiedras[ultimaPosicion] <= distanciaMinima)
        {
            saltos++;
            ultimaPosicion = i;
        }
    }
    if (longitudTotal - posicionesPiedras[numPiedras] <= distanciaMinima)
    {
        saltos++;
    }
    if (posicionesPiedras[1] - 1 <= distanciaMinima)
    {
        saltos++;
    }
    return saltos <= piedrasEliminar;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> longitudTotal >> numPiedras >> piedrasEliminar;
    posicionesPiedras.resize(numPiedras + 1);
    for (int i = 1; i <= numPiedras; ++i)
    {
        cin >> posicionesPiedras[i];
    }
    int izquierda = 0;
    int derecha = longitudTotal + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            izquierda = medio;
        }
        else
        {
            derecha = medio;
        }
    }
    if (verificar(derecha))
    {
        cout << izquierda << "\n";
    }
    else
    {
        cout << derecha << "\n";
    }
    return 0;
}

\(_{Solo pasó el ejemplo y \#1}\) \(_{:(}\)

Análisis del problema

Se pueden eliminar como máximo \(m\) piedras, \(l\) representa la distancia mínima entre dos piedras Si la distancia entre dos piedras es menor que \(l\), significa que esa piedra debe ser eliminada La respuesta de la búsqueda binaria es \(l\), cuanto mayor es \(l\), menos piedras cumplen el requisito

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100007;
int longitud, numPiedras, piedrasEliminar;
vector<int> posicionesPiedras;
bool verificar(int distanciaMinima)
{
    int piedrasEliminadas = 0;
    int posicionActual = 0;
    for (int i = 1; i <= numPiedras; i++)
    {
        if (posicionesPiedras[i] - posicionesPiedras[posicionActual] < distanciaMinima)
        {
            piedrasEliminadas++;
        }
        else
        {
            posicionActual = i;
        }
    }
    if (longitud - posicionesPiedras[posicionActual] < distanciaMinima)
    {
        piedrasEliminadas++;
    }
    return piedrasEliminadas <= piedrasEliminar;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> longitud >> numPiedras >> piedrasEliminar;
    posicionesPiedras.resize(numPiedras + 1);
    for (int i = 1; i <= numPiedras; ++i)
    {
        cin >> posicionesPiedras[i];
    }
    int izquierda = 0;
    int derecha = longitud + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            izquierda = medio;
        }
        else
        {
            derecha = medio;
        }
    }
    cout << izquierda << "\n";
    return 0;
}

T6. P1843 Vacas secando ropa

\(_{El enunciado es interesante:)}\)

Análisis del problema

Usar búsqueda binaria con la función verificar, dos amigos habituales

Pero ¡derecha debe ser lo suficientemente grande!!!

Usé \(5000 \times 5000 + 1\)

Si se pueden secar todas las prendas en el tiempo medio.

Reducir el intervalo derecho

Nota: ¡Declarar long long!

Código Aceptado:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 500007;
vector<int> humedad;
int nPrendas, secadoNatural, secadoArtificial;
bool verificar(int tiempo)
{
    int tiempoArtificial = 0;
    for (int i = 0; i < nPrendas; i++)
    {
        int humedadRestante = humedad[i] - secadoNatural * tiempo;
        if (humedadRestante > 0)
        {
            tiempoArtificial += ceil(humedadRestante * 1.0 / secadoArtificial);
        }
    }
    return tiempoArtificial <= tiempo;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> nPrendas >> secadoNatural >> secadoArtificial;
    humedad.resize(nPrendas);
    for (int i = 0; i < nPrendas; ++i)
    {
        cin >> humedad[i];
    }
    int izquierda = 0;
    int derecha = 5000 * 5000 + 1;
    while (izquierda + 1 < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        if (verificar(medio))
        {
            derecha = medio;
        }
        else
        {
            izquierda = medio;
        }
    }
    cout << derecha << "\n";
    return 0;
}

\(\mathbb {FIN}\)

Etiquetas: Búsqueda Binaria programación competitiva algoritmos Resolución de Problemas C++

Publicado el 7-22 15:14

Friki Work

Resumen de la prueba de búsqueda binaria del 17 de agosto

Resumen de la prueba de búsqueda binaria del 17 de agosto

Putnuación

Puntuación total

T1. P1873 [COCI 2011/2012 #5] EKO / Cortar árboles

Enlace al problema

Análisis del problema

Código Aceptado:

T2. B3880 [Información y Futuro 2015] Comprar madera

Enlace al problema

Código Incorrecto:

Análisis del problema

Análisis del error

Código Acpetado:

T3. P1182 Segmentación de array II

Enlace al problema

Problema previo P1181 Segmentación de array I

Código Aceptado:

Volviendo al problema actual (P1182)

Código Aceptado:

T4. B3629 Comer helados

Enlace al problema

Código Incorrecto:

Análisis del problema

Código Aceptado:

T5. P2678 [NOIP2015 Grupo avanzado] Saltando piedras

Enlace al problema

Código Incorrecto:

Análisis del problema

Código Aceptado:

T6. P1843 Vacas secando ropa

Análisis del problema

Código Aceptado:

\(\mathbb {FIN}\)

Etiquetas populares