สร้างสี่เหลี่ยมผืนผ้าใน C ++

สมมติว่าเรามีพื้นที่หน้าเว็บรูปสี่เหลี่ยมผืนผ้าเฉพาะ งานของเราคือออกแบบหน้าเว็บรูปสี่เหลี่ยมผืนผ้าซึ่งมีความยาว L และความกว้าง W ที่ตรงตามข้อกำหนดต่อไปนี้ -

• พื้นที่ของหน้าเว็บต้องเท่ากับพื้นที่เป้าหมายที่กำหนด

• ความกว้าง W ไม่ควรเกินความยาว L และ L>=W.

• ความแตกต่างระหว่าง L และ W ควรมีค่าน้อยที่สุด

ดังนั้น หากอินพุตเท่ากับ 4 เอาต์พุตจะเป็น [2,2] เนื่องจากพื้นที่เป้าหมายคือ 4 และวิธีการที่เป็นไปได้ทั้งหมดในการสร้างคือ [1,4], [2,2], [4 ,1]. ตามข้อกำหนดคือ 2 [1,4] ผิดกฎหมาย ตามข้อกำหนด 3 [4,1] ไม่เหมาะสมเมื่อเทียบกับ [2,2] ดังนั้นความยาว L คือ 2 และความกว้าง W คือ 2

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

• สำหรับการเริ่มต้น i :=รากที่สองของพื้นที่ เมื่อ i> 0 อัปเดต (ลด i ลง 1) ให้ทำ -

  • หากตัวดัดแปลงพื้นที่ i เท่ากับ 0 ดังนั้น −

    • กำหนดอาร์เรย์ v แทรก {area/i, i}

    • กลับ วี

• กลับ {-1, -1}

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> constructRectangle(int area) {
      for (int i = sqrt(area); i > 0; i--) {
         if (area % i == 0) {
            vector<int> v{ area / i, i };
            return v;
         }
      }
      return { -1, -1 };
   }
};
main(){
   Solution ob;
   print_vector(ob.constructRectangle(4));
}

อินพุต

4

ผลลัพธ์

[2, 2, ]