คำชี้แจงปัญหา
กำหนดอาร์เรย์ arr[] ของจำนวนบวก ค้นหาจำนวนชุดขั้นต่ำในอาร์เรย์ที่ตรงตามคุณสมบัติต่อไปนี้
- ชุดหนึ่งสามารถมีองค์ประกอบได้ไม่เกินสององค์ประกอบ องค์ประกอบทั้งสองไม่จำเป็นต้องต่อเนื่องกัน
- ผลรวมขององค์ประกอบของชุดควรน้อยกว่าหรือเท่ากับคีย์ที่กำหนด อาจสันนิษฐานได้ว่าคีย์ที่ระบุมากกว่าหรือเท่ากับองค์ประกอบอาร์เรย์ที่ใหญ่ที่สุด
ตัวอย่าง
ถ้า arr[] ={1, 2, 3, 4} และ k =5 จะสร้าง 2 คู่ต่อไปนี้ได้ -
{1, 4} และ {2, 3}
อัลกอริทึม
- จัดเรียงอาร์เรย์
- เริ่มตัวชี้สองตัวจากสองมุมของอาร์เรย์ที่จัดเรียง หากผลรวมของมันน้อยกว่าหรือเท่ากับคีย์ที่ให้มา เราจะสร้างชุดของพวกมัน มิฉะนั้น เราจะพิจารณาองค์ประกอบสุดท้ายเพียงอย่างเดียว
ตัวอย่าง
#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 << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Minimum set = 2
