Posible problema de lógica en el problema de C++

programación


¡El granjero John está cultivando N(1≤N≤2⋅10^5)plantas de espárragos en su granja! Sin embargo, algunas de sus plantas tienen diferencias genéticas, por lo que algunas crecerán más rápido que otras. La altura inicial de la iésima planta es de hola pulgadas y, después de cada día, la iésima planta crece ai pulgadas.
A FJ le gustan algunas de sus plantas más que otras y quiere que algunas plantas específicas sean más altas que otras. Le proporciona una serie de valores distintos t1……tn que contienen todos los números enteros de 0 a N−1 y quiere que la iésima planta tenga exactamente ti otras plantas que sean más altas que ella. Encuentre el número mínimo de días para que se satisfaga la solicitud de FJ, o determine que es imposible.
APORTE:
El primero constará de un número entero T, que denota el número de casos de prueba independientes (1≤T≤10)
La primera línea de cada caso de prueba consta de un número entero N.
La segunda línea consta de N enteros hi (1≤hi≤10^9) que denotan la altura inicial de la iésima planta en pulgadas.
La tercera línea consta de N enteros ai (1≤ai≤10^9) que denotan el número de pulgadas que crece la iésima planta cada día.
La cuarta línea consta de N enteros distintos ti que denotan la matriz que le proporciona FJ.
Se garantiza que la suma de N en todos los casos de prueba no exceda 2⋅10^5

PRODUCCIÓN:
Salida T líneas, la respuesta a cada caso de prueba en una línea diferente. Si no es posible, genere −1.
Tenga en cuenta que el gran tamaño de los números enteros involucrados en este problema puede requerir el uso de tipos de datos enteros de 64 bits (por ejemplo, “long long” en C/C++).
ENTRADA DE MUESTRA 1:
6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

SALIDA DE MUESTRA 1:
0
3
2
5
-1
-1

En la primera entrada de muestra, hay 6 casos de prueba.
En el primer caso de prueba, solo hay una planta, por lo que la condición se cumple el día 0.
En el segundo caso de prueba, necesitamos que la primera planta sea más corta que la segunda. Después del día 1, las alturas son 15 y 13. Después del día 2, las alturas son 23. Después del día 3, las alturas son 31 y 33, y ese es el primer día en el que se cumple la condición.
Los casos de prueba tercero y cuarto son similares al segundo.
En el quinto caso de prueba, ambas plantas comienzan con una altura inicial de 7 y una tasa de crecimiento de 8. Por lo tanto, siempre tendrán alturas idénticas y, por lo tanto, la condición nunca se cumple.
En el sexto caso de prueba, la condición no se cumple inicialmente y las tasas de crecimiento son las mismas. Por tanto, la condición nunca podrá satisfacerse.
ENTRADA DE MUESTRA 2:
2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

SALIDA DE MUESTRA 2:
4
7

En la segunda entrada de muestra, hay 2 casos de prueba.
En el primer caso de prueba, las alturas finales después del día 4 son 19, 20, 21, 18, 16.
En el segundo caso de prueba, las alturas finales después del día 7 son 25, 17, 19, 35, 36.

Lo que he probado:

Probé estos 2 códigos (muy ligeramente) diferentes:
1.

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

using namespace std;

bool isPossible(const vector<int>& h, const vector<int>& a, const vector<int>& t, long long days) {
    int n = h.size();
    vector<pair<long long, int>> heights;

    for (int i = 0; i < n; ++i) {
        heights.push_back({h[i] + days * a[i], t[i]});
    }

    sort(heights.begin(), heights.end(), greater<pair<long long, int>>());

    for (int i = 0; i < n; ++i) {
        if (heights[i].second > i) {
            return false;
        }
    }

    return true;
}

long long minDays(const vector<int>& h, const vector<int>& a, const vector<int>& t) {
    int n = h.size();

    if (n <= 1) {
        return 0; // No need for days if there are 0 or 1 plants.
    }

    long long low = 0, high = 1e18, result = -1;  // Adjusted upper limit

    // Handle smaller inputs efficiently
    if (n <= 2) {
        for (long long i = 0; i <= 1e3; ++i) {
            if (isPossible(h, a, t, i)) {
                result = i;
                break;
            }
        }
    } else if (n <= 50) {
        for (long long i = 0; i <= 1e3; ++i) {
            if (isPossible(h, a, t, i)) {
                result = i;
                break;
            }
        }
    } else {
        while (low <= high) {
            long long mid = low + (high - low) / 2;

            if (isPossible(h, a, t, mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }

    return result;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> h(N), a(N), t(N);

        for (int i = 0; i < N; ++i) {
            cin >> h[i];
        }

        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }

        for (int i = 0; i < N; ++i) {
            cin >> t[i];
        }

        long long result = minDays(h, a, t);
        cout << result << endl;
    }

    return 0;
}

2.

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

using namespace std;

bool isPossible(const vector<int>& h, const vector<int>& a, const vector<int>& t, long long days) {
    int n = h.size();
    vector<pair<long long, int>> heights;

    for (int i = 0; i < n; ++i) {
        heights.push_back({h[i] + days * a[i], t[i]});
    }

    sort(heights.begin(), heights.end(), greater<pair<long long, int>>());

    for (int i = 0; i < n; ++i) {
        if (heights[i].second > i) {
            return false;
        }
    }

    return true;
}

long long minDays(const vector<int>& h, const vector<int>& a, const vector<int>& t) {
    int n = h.size();

    long long low = 0, high = 2e9, result = -1;  // Adjusted upper limit for large inputs

    // Handle smaller inputs efficiently
    if (n <= 2) {
        for (long long i = 0; i <= 2e3; ++i) {  // Adjusted range for small inputs
            if (isPossible(h, a, t, i)) {
                result = i;
                break;
            }
        }
    } else if (n <= 50) {
        for (long long i = 0; i <= 2e3; ++i) {  // Adjusted range for medium inputs
            if (isPossible(h, a, t, i)) {
                result = i;
                break;
            }
        }
    } else {
        while (low <= high) {
            long long mid = low + (high - low) / 2;

            if (isPossible(h, a, t, mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }

    return result;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> h(N), a(N), t(N);

        for (int i = 0; i < N; ++i) {
            cin >> h[i];
        }

        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }

        for (int i = 0; i < N; ++i) {
            cin >> t[i];
        }

        long long result = minDays(h, a, t);
        cout << result << endl;
    }

    return 0;
}

Solución 1

Este es el mismo problema que ¿Cómo soluciono este problema para todas las restricciones?[^]. Solo necesita adaptarse al crecimiento de los espárragos, en lugar de que los bastones de caramelo se encojan.

Solución 2

Necesito ayuda también, si lo resolviste por favor házmelo saber.

コメント

タイトルとURLをコピーしました