ข้อความโจทย์
กำหนดอาร์เรย์ arr[] ของจำนวนบวก หาจำนวนเซตน้อยที่สุดในอาร์เรย์ที่สอดคล้องกับเงื่อนไขดังนี้
- เซตหนึ่งสามารถมีสมาชิกได้สูงสุด 2 ตัว สองสมาชิกไม่จำเป็นต้องติดกัน
- ผลรวมของสมาชิกในเซตควรน้อยกว่าหรือเท่ากับค่า Key ที่กำหนด สมมติว่า Key มากกว่าหรือเท่ากับสมาชิกที่ใหญ่ที่สุดในอาร์เรย์
ตัวอย่าง
ถ้า arr[] = {1, 2, 3, 4} และ k = 5 สามารถสร้าง 2 คู่ได้ −
{1, 4} และ {2, 3}
อัลกอริทึม
- เรียงลำดับอาร์เรย์
- เริ่มต้นพอยน์เตอร์สองตัวจากสองมุมของอาร์เรย์ที่เรียงแล้ว หากผลรวมของพวกเขาน้อยกว่าหรือเท่ากับ Key ให้จับคู่เป็นเซต มิฉะนั้นให้พิจารณาสมาชิกสุดท้ายเพียงตัวเดียว
ตัวอย่าง
#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
