C++ หาจำนวนกล่องที่มองเห็นได้หลังจากใส่กล่องเล็กเข้าไปในกล่องใหญ่

เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ที่มีขนาดของกล่อง ตอนนี้เราได้รับเงื่อนไขว่าเราสามารถใส่กล่องเล็กเข้าไปในกล่องใหญ่ได้ ถ้ากล่องใหญ่มีขนาดอย่างน้อยสองเท่าของกล่องเล็ก ตอนนี้เราต้องหาว่ามีกล่องที่มองเห็นได้กี่กล่อง เช่น

Input : arr[] = { 1, 3, 4, 5 } Output : 3 ใส่กล่องขนาด 1 เข้าไปในกล่องขนาด 3
Input : arr[] = { 4, 2, 1, 8 } Output : 1

วิธีการแก้ปัญหา

ในปัญหานี้ วิธีของเราจะเป็นการจัดเรียงอาร์เรย์ ตอนนี้เมื่อเราเคลื่อนไปข้างหน้า เราจะ Push สมาชิกเข้า Queue ตอนนี้เราจะดูว่าสมาชิกปัจจุบันใหญ่กว่าหรือเท่ากับสองเท่าของสมาชิกหน้าสุดของ Queue หรือไม่ ถ้าเป็นจริง เรา Pop สมาชิกหน้าสุด ตอนนี้เรา Push สมาชิกปัจจุบันเข้า Queue คำตอบของเราจะเป็นขนาดของ Queue ในท้ายที่สุด

ตัวอย่าง

#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 < n; i++) { 
        int curr = q.front(); 
        if (arr[i] >= 2 * curr) 
            q.pop(); 
        q.push(arr[i]); 
    } 
    cout << q.size() << "\n"; 
    return 0; 
}

ผลลัพธ์

3

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหาจำนวนกล่องที่มองเห็นได้หลังจากใส่กล่องเล็กเข้าไปในกล่องใหญ่ เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์