เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ที่มีขนาดของกล่อง ตอนนี้เราได้รับเงื่อนไขว่าเราสามารถใส่กล่องขนาดเล็กลงในกล่องที่ใหญ่กว่าได้หากกล่องที่ใหญ่กว่านั้นมีขนาดอย่างน้อยสองเท่าของกล่องที่เล็กกว่า ตอนนี้เราต้องกำหนดจำนวนช่องที่มองเห็นได้ เป็นต้น
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 และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์