Construct the Rectangle ใน 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 := รากที่สองของ area ลงมาจนถึง 1: ถ้า area mod i เท่ากับ 0: กำหนดอาร์เรย์ v ใส่ {area/i, i}, คืนค่า v
คืนค่า {-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));
}

อินพุต

เอาต์พุต

[2, 2, ]