Étant donné un tableau chiffres de longueur N qui contient deux sorts de nombres, l’un ayant la valeur zérole second qui est un entier positif, la tâche consiste à collecter les nombres des opérations ci-dessous et à renvoyer la valeur maximale que vous pouvez collecter.
- Si le nombre donné est un entier positif, alors c’est votre choix, si vous pouvez le mettre en haut de la file d’attente ou non.
- Sinon, si le nombre est zéro, choisissez le nombre le plus élevé dans la file d’attente et supprimez-le.
Exemples:
Saisir: N = 7, nombres = (1, 2, 3, 0, 4, 5, 0)
Sortir: 8
Explication: Pour maximiser la valeur totale, effectuez l’opération suivante lors de l’itération de nums() :
nums(0) = 1, placé en haut de la file d’attente. La file d’attente devient : (1)
nums(1) = 2, placé en haut de la file d’attente. La file d’attente devient : (2, 1)
nums(2) = 3, placé en haut de la file d’attente. La file d’attente devient : (3, 2, 1)
nums(3) = 0, choisissez la valeur supérieure de la file d’attente et supprimez-la. Complete val = 3, et la file d’attente devient : (2, 1)
nums(4) = 4, placé en haut de la file d’attente. La file d’attente devient : (4, 2, 1)
nums(5) = 5, placé en haut de la file d’attente. La file d’attente devient : (5, 4, 2, 1)
nums(6) = 0, choisissez la valeur supérieure de la file d’attente et supprimez-la. Valeur totale = 3 + 5 = 8, et la file d’attente devient : (4, 2, 1)
Valeur de retour = 8.Saisir: N = 8, nombres = (5, 1, 2, 0, 0, 4, 3, 0)
Sortir: 11
Explication: Pour maximiser la valeur totale, effectuez l’opération suivante lors de l’itération de nums() :
nums(0) = 5, placé en haut de la file d’attente. La file d’attente devient : (5)
nums(1) = 1, ignorez ce nombre. File d’attente restante : (5)
nums(2) = 2, placé en haut de la file d’attente. La file d’attente devient : (2, 5)
nums(3) = 0, choisissez la valeur supérieure de la file d’attente et supprimez-la. Valeur totale = 0 + 2 = 2, et la file d’attente devient : (5)
nums(4) = 0, choisissez la valeur supérieure de la file d’attente et supprimez-la. Valeur totale = 2 + 5 = 7, et la file d’attente devient : ( )
nums(5) = 4, placé en haut de la file d’attente. La file d’attente devient : (4)
nums(6) = 3, ignorez ce nombre. File d’attente restante : (4)
nums(7) = 0, choisissez la valeur supérieure de la file d’attente et supprimez-la. Valeur totale = 7 + 4 = 11, et la file d’attente devient : ( )
Valeur de retour = 11.
Approche: Pour résoudre le problème, suivez l’idée ci-dessous :
Nous utiliserons une décroissante File d’attente de priorité et y stocker les entiers positifs, lorsque nous rencontrerons zéro, nous prendrons l’élément peek () (s’il n’est pas vide) de la file d’attente prioritaire et l’ajouterons à la variable val.
Voici les étapes de l’approche ci-dessus :
- Initialiser une file d’attente à priorité décroissante.
- Itérer le tableau donné,
- Si vous rencontrez un entier positif, ajoutez-le à la file d’attente prioritaire.
- Sinon, si vous rencontrez un zéro, vérifiez si la file d’attente prioritaire est vide ou non. S’il n’est pas vide, supprimez-en l’élément supérieur et ajoutez-le à la variable val qui contient la somme actuelle de la valeur maximale.
- Renvoyez la réponse finale val.
Vous trouverez ci-dessous le code de l’approche ci-dessus :
Java
|
|
Most worth is : 11
Complexité temporelle : O(N * log(N))
Espace Auxiliaire : SUR)
