C++ Số hộp hiển thị sau khi lồng nhau

Cho mảng kích thước hộp. Hộp nhỏ có thể lồng vào hộp lớn nếu hộp lớn ≥ 2× hộp nhỏ. Tìm số hộp hiển thị (không bị lồng). Ví dụ:

Input: {1,3,4,5} → Output: 3 (1 lồng vào 3)
Input: {4,2,1,8} → Output: 1

Phương pháp giải

Sắp xếp mảng. Dùng hàng đợi: đẩy phần tử nhỏ nhất. Duyệt các phần tử còn lại: nếu phần tử hiện tại ≥ 2× front queue → pop front. Luôn push phần tử hiện tại. Kết quả = size(queue).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1,2,3,4,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    queue<int> q;
    sort(arr, arr+n);
    q.push(arr[0]);

    for (int i=1; i= 2*curr) q.pop();
        q.push(arr[i]);
    }
    cout << q.size() << "\n";
    return 0;
}

Kết quả

3

Kết luận

Đã giải bài toán hộp hiển thị sau lồng nhau bằng sắp xếp + hàng đợi tham lam. Code C++ chuyển được sang C, Java, Python. Hy vọng hữu ích.