Để giải quyết một vấn đề trong đó chúng ta được cung cấp một mảng chứa kích thước của các hộp. Bây giờ chúng ta được đưa ra một điều kiện là chúng ta có thể nhét một hộp nhỏ hơn vào trong một hộp lớn hơn nếu hộp lớn hơn ít nhất gấp đôi kích thước của hộp nhỏ hơn. Bây giờ chúng ta phải xác định xem có bao nhiêu hộp có thể nhìn thấy được, chẳng hạn.
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 Phương pháp tiếp cận để tìm giải pháp
Trong vấn đề này, cách tiếp cận của chúng ta sẽ là sắp xếp mảng của chúng ta ngay bây giờ khi chúng ta tiến về phía trước. Chúng tôi đẩy các phần tử vào một hàng đợi ngay bây giờ. Chúng tôi sẽ xem liệu phần tử hiện tại có lớn hơn hoặc bằng hai lần phần tử phía trước của hàng đợi hay không khi chúng tôi tiến hành. Nếu nó là đúng, chúng tôi bật phần tử phía trước ngay bây giờ. Cuối cùng, chúng tôi đẩy phần tử hiện tại vào hàng đợi. Câu trả lời của chúng tôi sẽ là kích thước của hàng đợi của chúng tôi ở cuối.
Ví dụ
#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;
} Đầu ra
3
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm Số lượng hộp có thể nhìn thấy sau khi đặt một hộp vào bên trong hộp khác. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.