จำนวนสี่เหลี่ยมขนานสูงสุดจากเส้นตรงที่กำหนดใน C++

ภาพรวมปัญหา

หาจำนวนสี่เหลี่ยมขนานสูงสุดที่สร้างได้จาก N เส้นตรง โดยแต่ละเส้นใช้ได้สูงสุด 1 สี่เหลี่ยมขนาน

ตัวอย่าง

Input: Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}
Output: 2
Explanation: สี่เหลี่ยมขนาน 2 รูป: ด้าน (8,1,8,1) และ (3,3,3,3)

Input: Arr[] = {7, 9, 9, 7}
Output: 1

แนวทางแก้ปัญหา

• นับความถี่ของแต่ละความยาวเส้นตรง
• สี่เหลี่ยมขนานที่มี 4 ด้านเท่ากัน: freq[i] / 4
• เศษที่เหลือ 2-3 ด้าน: นับจำนวนความยาวที่เหลือ ≥ 2 ด้าน แล้วหาร 2 (เพราะต้องการ 2 คู่)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int MaxParr(int N, int Arr[]) {
    int L = Arr[0];
    for (int i = 1; i < N; i++) if (Arr[i] > L) L = Arr[i];
    L++;
    
    int Freq[L] = {0};
    for (int i = 0; i < N; i++) Freq[Arr[i]]++;
    
    int count = 0;
    for (int i = 0; i < L; i++) {
        count += Freq[i] / 4;
        Freq[i] %= 4;
    }
    
    int left = 0;
    for (int i = 0; i < L; i++)
        if (Freq[i] >= 2) left++;
    
    count += left / 2;
    return count;
}

int main() {
    int N = 10;
    int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3 };
    cout << MaxParr(N, Arr);
    return 0;
}

ผลลัพธ์

2