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

สมมุติว่าเรามีความกว้างและความสูงเท่ากับ N รูปสี่เหลี่ยมผืนผ้า เราต้องหาจำนวนสี่เหลี่ยมขั้นต่ำที่เหลือหลังจากใส่เข้าไปในอีกอัน ดังนั้น ถ้า W1 และ W2 เป็นความกว้างของสี่เหลี่ยม R1 และ R2 ตามลำดับ และ H1 และ H2 เป็นความสูงของ R1 และ R2 ตามลำดับ ดังนั้นหาก W1

ดังนั้น หากอินพุตเป็น {{ 30, 45 }, { 15, 15 }, { 45, 30 },{60, 75 }} ผลลัพธ์จะเป็น 2 เนื่องจากหนึ่งในวิธีที่เป็นไปได้คือการแทรกสี่เหลี่ยมผืนผ้าที่สอง เข้าไปในอันแรกแล้วแทรกสี่เหลี่ยมนั้นเข้าไปในอันที่สี่ เหลือสี่เหลี่ยมที่สามและสี่

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของกล่อง

• จัดเรียงกล่องอาร์เรย์ตามขนาด

• กำหนดอาร์เรย์ที่ซ้อนกันของคู่

• แทรกกล่อง[n - 1] ที่ส่วนท้ายของการซ้อน

• สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ขวา :=ขนาดของซ้อน

  • ขณะที่ซ้าย <=ขวา ทำ:

    • กลาง :=(ขวา + ซ้าย) / 2

    • ถ้าความสูงของ nested[mid] เท่ากับความสูงของ box[i] หรือ width of nested[mid] <=width of boxes[i] แล้ว −

      • ซ้าย :=กลาง + 1

    • มิฉะนั้น

      • ขวา :=กลาง - 1

  • ถ้าเหลือเท่ากับขนาดของซ้อนกันแล้ว −

    • แทรกกล่อง[i] ที่ส่วนท้ายของการซ้อน

  • มิฉะนั้น

    • ความกว้างของซ้อน[ซ้าย] :=ความกว้างของกล่อง[i]

    • ความสูงของซ้อน[ซ้าย] :=ความสูงของกล่อง[i]

• ส่งคืนขนาดที่ซ้อนกัน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;bool comp (const pair&L, const pair&R) { if (L.first ==R.first ) คืนค่า L.second> R.second; คืนค่า L.first > &boxes) { int n =boxes.size(); sort(boxes.begin(), boxes.end(), คอมพ์); vector=0; --i) { int right =nested.size() - 1, left =0; ในขณะที่ (ซ้าย <=ขวา) { int mid =(ขวา + ซ้าย) / 2; if (nested[mid].first ==boxes[i].first || nested[mid].second <=boxes[i].second) เหลือ =กลาง + 1; อย่างอื่นขวา =กลาง - 1; } if (left ==nested.size()) nested.push_back(boxes[i]); อื่น { ซ้อน[ซ้าย].วินาที =กล่อง[i].วินาที; ซ้อน[left].first =กล่อง[i].first; } } ส่งคืน nested.size();}int main() { vector> boxes ={{30, 45}, {15,15}, {45,30},{60,75} }; cout <<สี่เหลี่ยมผืนผ้า (กล่อง);}

อินพุต

ผลลัพธ์

2