หาคู่จากอาร์เรย์ที่ให้ค่า nCr สูงสุดใน C++

แนวคิด

กำหนดอาร์เรย์ arr[] ของจำนวนเต็มบวก n ตัว หาคู่ arr[i], arr[j] ที่ทำให้ nCr = arr[i]Carr[j] มีค่าสูงสุด

หลักการ: - nCr เพิ่มขึ้นเมื่อ n เพิ่ม (n+1)Cr > nCr → เลือก n = max(arr) - nCr = nC(n-r) → ค่าสูงสุดอยู่ที่ r ≈ n/2 - n คี่: max ที่ n/2 และ n/2+1 - n คู่: max ที่ n/2

วิธีการแก้ปัญหา

1. เรียงอาร์เรย์, ให้ N = ค่าสูงสุด
2. ถ้า N คี่: หาค่าในอาร์เรย์ที่ใกล้ N/2 และ N/2+1 มากที่สุด เลือกที่ใกล้กว่า
3. ถ้า N คู่: หาค่าที่ใกล้ N/2 มากที่สุด

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

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

void printMaxValPair1(vector<long long>& v1, int n1){
    sort(v1.begin(), v1.end());
    long long N1 = v1[n1 - 1];
    if (N1 % 2 == 1) {
        long long first_maxima1 = N1 / 2;
        long long second_maxima1 = first_maxima1 + 1;
        long long ans1 = 3e18, ans2 = 3e18;
        long long from_left1 = -1, from_right1 = -1;
        long long from = -1;
        for (long long i = 0; i < n1; ++i) {
            if (v1[i] > first_maxima1) { from = i; break; }
            else {
                long long diff = first_maxima1 - v1[i];
                if (diff < ans1) { ans1 = diff; from_left1 = v1[i]; }
            }
        }
        from_right1 = v1[from];
        long long diff1 = first_maxima1 - from_left1;
        long long diff2 = from_right1 - second_maxima1;
        if (diff1 < diff2) cout << N1 << " " << from_left1;
        else cout << N1 << " " << from_right1;
    } else {
        long long maxima = N1 / 2;
        long long ans1 = 3e18;
        long long R = -1;
        for (long long i = 0; i < n1 - 1; ++i) {
            long long diff = abs(v1[i] - maxima);
            if (diff < ans1) { ans1 = diff; R = v1[i]; }
        }
        cout << N1 << " " << R;
    }
}

int main(){
    vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
    int n1 = v1.size();
    printMaxValPair1(v1, n1);
    return 0;
}

ผลลัพธ์

6 3