¡Por favor! ¡Cómo resolver el MLE en código!

programación


Me encontré con esta pregunta:

Las vacas del granjero John son muy golosas y disfrutan especialmente comiendo bastones de caramelo. FJ tiene N vacas en total, cada una con una determinada altura inicial y quiere alimentarlas con M bastones de caramelo, cada uno también de diferente altura (1≤N,M≤2⋅10^5).
FJ planea alimentar a las vacas con los bastones de caramelo uno por uno, en el orden en que aparecen en la entrada. Para alimentar a sus vacas con un bastón de caramelo, colgará el bastón de caramelo de modo que inicialmente toque el suelo. Luego, las vacas se alinearán una por una, en el orden dado por la entrada, y subirán al bastón de caramelo, cada una comiendo hasta su altura (ya que no pueden llegar más alto). El bastón de caramelo permanece suspendido en el lugar donde se instaló inicialmente y no se baja al suelo, incluso después de que las vacas se comen la base del bastón de caramelo. Es posible que una vaca no coma nada durante su turno, si la base del bastón de caramelo ya está por encima de la altura de esa vaca. Después de que cada vaca ha tenido su turno, las vacas crecen en altura según la cantidad de unidades de bastón de caramelo que comieron, y el granjero John cuelga el siguiente bastón de caramelo y las vacas repiten el proceso nuevamente (siendo la vaca 1 nuevamente la primera en comenzar a comer el bastón de caramelo). siguiente bastón de caramelo). Nota especial: El bastón de caramelo flota en el aire, por ejemplo cuando una vaca con una altura de 2 alcanza un bastón de caramelo con una altura de 3, se come las 2 unidades (1 y 2), y la tercera unidad del bastón de caramelo. todavía flota en el aire, por lo que sólo las vacas que tienen una altura ≥ 2 pueden alcanzarlo y comérselo.

FORMATO DE ENTRADA (tubería estándar):
La primera línea contiene N y M.
La siguiente línea contiene las alturas iniciales de las Ncows, cada una en el rango [1,10^9].
La siguiente línea contiene las alturas de los bastones de caramelo M, cada uno en el rango [1,10^9].

FORMATO DE SALIDA (salida estándar de tubería):
Las alturas finales de cada una de las N vacas en líneas separadas.
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:
3 2
3 2 5
6 1
SALIDA DE MUESTRA:
7
2
7 Explicación:
El primer bastón de caramelo mide 6 unidades de alto.
1. La primera vaca come la porción del primer bastón de caramelo hasta la altura 3, después de lo cual la porción restante del primer bastón de caramelo ocupa las alturas. [3,6].
2. La segunda vaca no es lo suficientemente alta como para comerse la porción restante del primer bastón de caramelo.
3. La tercera vaca come dos unidades adicionales del primer bastón de caramelo. La porción restante del primer bastón de caramelo, ocupando alturas. [5,6]no se come.
Luego, cada vaca crece según la cantidad que comió, por lo que las alturas de las vacas se vuelven [3+3,2+0,5+2]=[6,2,7].
El segundo bastón de caramelo mide 1 unidad de alto y la primera vaca se lo come todo.

PUNTUACIÓN:

* Entradas 2-10: N,M≤10^3
* Entradas 11-14: Sin restricciones adicionales.

Y aquí está mi respuesta de C++:

C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,m;
    cin>>n>>m;
    ll heightcow[n];
    for(int i=1;i<=n;i++){
        cin>>heightcow[i];
    }
    ll finalcow[n];
    for(ll i=1;i<=n;i++){
        finalcow[i]=heightcow[i];
    }
    ll heightcane[m];
    for(ll i=1;i<=m;i++){
        cin>>heightcane[i];
    }
    for(ll j=1;j<=m;j++){//cane
        bool statcane[m];
        for(ll i=1;i<=heightcane[j];i++){
            statcane[i]=true;
        }
        for(ll i=1;i<=n;i++){//cow
            for(ll k=1;k<=heightcow[i];k++){
                if(statcane[k]==true){
                    statcane[k]=false;
                    finalcow[i]++;
                }
            }
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<finalcow[i]<<endl;
    }
    return 0;
}

Lo que he probado:

No tengo idea de qué hacer, soy titular. ¡Por favor ayuda!

Solución 1

Lo primero que nota sobre el código es que los sectores se extienden más allá del final de las matrices:

C++
ll heightcow[n] = { 3, 2, 5 };
ll heightcane[m] = { 6, 1 };
ll finalcow[n];

for (ll i = 1; i <= n; i++) {
    finalcow[i] = heightcow[i];
}

Las matrices siempre comienzan en 0 y terminan en n-1.

コメント

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