Số hình bình hành tối đa từ các đoạn thẳng cho trước C++

Cho N đoạn thẳng với độ dài cho trước. Mỗi đoạn chỉ dùng trong tối đa 1 hình bình hành. Hình bình hành cần 4 cạnh: 2 cặp cạnh đối diện bằng nhau. Tìm số hình bình hành tối đa có thể tạo.

Ví dụ

Input: {8, 3, 1, 3, 8, 7, 1, 3, 5, 3} → Output: 2
Giải thích: Hình 1: 4 cạnh 3. Hình 2: 2 cạnh 8 + 2 cạnh 1.

Input: {7, 9, 9, 7} → Output: 1 (2 cạnh 7 + 2 cạnh 9)

Thuật toán

1. Đếm tần suất mỗi độ dài.
2. Ưu tiên tạo hình bình hành từ 4 cạnh bằng nhau (hình thoi/vuông): mỗi 4 đoạn cùng độ dài → 1 hình.
3. Sau đó, các đoạn dư (2 hoặc 3 đoạn) ghép thành cặp: mỗi 2 đoạn cùng độ dài → 1 "cặp cạnh". 2 cặp cạnh khác nhau → 1 hình bình hành.

Chương trình C++

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

int maxParallelograms(int N, int arr[]) {
    // Tìm độ dài lớn nhất để cấp phát mảng tần suất
    int maxLen = *max_element(arr, arr + N);
    vector freq(maxLen + 1, 0);
    for (int i = 0; i < N; i++) freq[arr[i]]++;
    
    int count = 0;
    // 1. Hình bình hành 4 cạnh bằng nhau
    for (int i = 0; i <= maxLen; i++) {
        count += freq[i] / 4;
        freq[i] %= 4;
    }
    
    // 2. Ghép các cặp cạnh còn lại (2 cạnh bằng nhau)
    int pairs = 0;
    for (int i = 0; i <= maxLen; i++)
        if (freq[i] >= 2) pairs++;
    
    count += pairs / 2; // 2 cặp → 1 hình
    return count;
}

int main() {
    int arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
    int N = 10;
    cout << maxParallelograms(N, arr); // Output: 2
    return 0;
}

Kết quả

2