Số phân vùng tối thiểu kích thước tối đa 2 và tổng giới hạn bởi giá trị cho trước trong C++

Đề bài

Cho mảng arr[] các số dương, tìm số lượng tập hợp tối thiểu trong mảng thỏa mãn tính chất sau:

• Một tập hợp có thể chứa tối đa hai phần tử. Hai phần tử không cần phải liền kề.
• Tổng các phần tử của tập hợp nên nhỏ hơn hoặc bằng Key cho trước. Có thể giả định Key lớn hơn hoặc bằng phần tử lớn nhất của mảng.

Ví dụ

Nếu arr[] = {1, 2, 3, 4} và k = 5 thì có thể tạo 2 cặp sau −

{1, 4} và {2, 3}

Thuật toán

• Sắp xếp mảng
• Bắt đầu hai con trỏ từ hai góc của mảng đã sắp xếp. Nếu tổng của chúng nhỏ hơn hoặc bằng key cho trước, ta tạo tập hợp từ chúng, ngược lại ta xem xét phần tử cuối cùng một mình.

Ví dụ

#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
    int i, j;
    sort(arr, arr + n);
    for (i = 0, j = n - 1; i <= j; ++i) {
        if (arr[i] + arr[j] <= key) {
            --j;
        }
    }
    return i;
}
int main() {
    int arr[] = {1, 2, 3, 4};
    int key = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tập hợp tối thiểu = " << getMinSets(arr, n, key) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Tập hợp tối thiểu = 2