Programme C++ : recherchez le nombre de cases visibles après avoir placé une case dans une autre case

Pour résoudre un problème, on nous donne un tableau contenant les dimensions de la boîte. Nous avons maintenant une condition : si la taille de la grande boîte est au moins deux fois supérieure à celle de la petite boîte, alors nous pouvons mettre la petite boîte dans la grande boîte. Nous devons maintenant déterminer combien de cases visibles il y a, par exemple.

Input : arr[] = { 1, 3, 4, 5 }
Output : 3
Put a box of size 1 in the box of size 3.

Input : arr[] = { 4, 2, 1, 8 }
Output : 1

La façon de trouver la solution

Dans ce problème, notre approche consiste à trier le tableau au fur et à mesure. Nous poussons maintenant l'élément dans la file d'attente. Au fur et à mesure que nous progressons, nous vérifierons si l'élément actuel est supérieur ou égal à deux fois la taille de l'élément en début de file d'attente. Si c'est vrai, nous faisons maintenant apparaître l'élément précédent. Enfin, nous poussons l'élément actuel dans la file d'attente. Notre réponse sera la taille de la file d’attente à la fin.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = { 1, 2, 3, 4, 5, 6 }; // given array containing the size of our boxes
    int n = sizeof(arr) / sizeof(arr[0]); // size of our array
    queue<int> q;
    sort(arr, arr + n); // sorting our array
    q.push(arr[0]); // pushing the smallest element in the front
    for (int i = 1; i < n; i++) { // traversing the array
        int curr = q.front(); // current element
        if (arr[i] >= 2 * curr) // if the size of the current box is greater than twice
                               // of the box in front so we pop the front
            q.pop();

        q.push(arr[i]); // pushing the current element in the queue
    }
    cout << q.size() << "\n"; // our answer
    return 0;
}

Sortie

3

Conclusion

Dans ce tutoriel, nous avons résolu le problème de trouver le nombre de cases visibles après avoir placé une case dans une autre case. Nous avons également appris le programme C++ pour ce problème et la méthode complète (générique) pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!