เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ที่มีขนาดของกล่อง ตอนนี้เราได้รับเงื่อนไขว่าเราสามารถใส่กล่องขนาดเล็กลงในกล่องที่ใหญ่กว่าได้หากกล่องที่ใหญ่กว่านั้นมีขนาดอย่างน้อยสองเท่าของกล่องที่เล็กกว่า ตอนนี้เราต้องกำหนดจำนวนช่องที่มองเห็นได้ เป็นต้น
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 แนวทางในการหาแนวทางแก้ไข
ในปัญหานี้ แนวทางของเราคือจัดเรียงอาร์เรย์ของเราทันทีเมื่อเราก้าวไปข้างหน้า เราผลักองค์ประกอบไปที่คิวตอนนี้ เราจะดูว่าองค์ประกอบปัจจุบันมากกว่าหรือเท่ากับสองเท่าขององค์ประกอบด้านหน้าของคิวในขณะที่เราดำเนินการ หากเป็นเรื่องจริง เราจะเปิดองค์ประกอบด้านหน้าทันที สุดท้าย เราผลักองค์ประกอบปัจจุบันในคิว คำตอบของเราจะอยู่ที่ขนาดของคิวของเราในตอนท้าย
ตัวอย่าง
#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;
} ผลลัพธ์
3
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาเพื่อค้นหาจำนวนกล่องที่มองเห็นได้หลังจากใส่กล่องหนึ่งลงในอีกกล่องหนึ่ง นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
