Partage
  • Partager sur Facebook
  • Partager sur Twitter

Problème d’algorithmique : recouvrir des trous

Trouver nombre maximal d'éléments "recouvrables" dans un tableau

    12 octobre 2024 à 20:56:39

    Bonsoir à tous.
    J'ai besoin d'un peu d'aide pour ce problème :
    "Vous devez recouvrir n trous à l'aide de nbCiment ciment et d'une planche de longueur longueurPlanche.
    Chaque trou a une profondeur x, il ne peut être recouvert qu'à l'aide d'au moins x ciment (donc il faut que nbCiment >= x) ou alors de la planche.
    Vous n'avez qu'une seule planche et elle vous permet de recouvrir longueurPlanche trous consécutifs peu importe leurs profondeurs.
    Vous devez trouver et afficher le nombre maximal de trous consécutifs qu'on peut recouvrir.
    En entrée on vous fournir dans l'ordre : n, nbCiment et longueurPlanche. Puis on vous donne n entiers : les profondeurs des n trous. (ATTENTION : n peut atteindre jusqu'à 10^6 !)
    Exemple :
    Entrée :
    ```
    8 6 2
    3 4 1 9 4 1 7 1
    ```
    Sortie :
    ```5```
    Commentaires de l'exemple :
    On recouvre d'abord les trous 2 et 3 avec du ciment. Puis on pose la planche pour recouvrir les trous 4 et 5 et avec le ciment restant on recouvre le trou 6."
    Vu que n peut atteindre jusqu'à 10^6, je pense que la solution est en O(n). Ça doit sûrement être un algorithme glouton, mais je ne vois pas bien comment le réaliser. Ou alors des balayages...
    Si vous avez une idée, n'hésitez pas !
    Merci d'avance.
    Bonne continuation :)
    • Partager sur Facebook
    • Partager sur Twitter

    Problème d’algorithmique : recouvrir des trous

    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
    • Editeur
    • Markdown