Tìm cặp số cho giá trị nCr lớn nhất từ mảng trong C++

Khái niệm

Cho mảng arr[] n số nguyên dương, tìm hai phần tử arr[i], arr[j] sao cho C(arr[i], arr[j]) lớn nhất. Nếu nhiều cặp hợp lệ, in ra một cặp bất kỳ.

Ví dụ: arr[] = {4, 1, 2} → 4 2 (C(4,2)=6 là lớn nhất).

Phương pháp

C(n,r) tăng theo n (cố định r). Do đó chọn n = max(arr). Với n cố định, C(n,r) đạt cực đại tại r ≈ n/2:

• n lẻ: cực đại tại n/2 và n/2+1.
• n chẵn: cực đại tại n/2.

Ví dụ (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, second_maxima1 = first_maxima1+1;
        long long ans1=3e18, ans2=3e18, from_left1=-1, from_right1=-1, 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, diff2=from_right1-second_maxima1;
        if(diff1<diff2) cout<<N1<<" "<<from_left1;
        else cout<<N1<<" "<<from_right1;
    } else {
        long long maxima=N1/2, ans1=3e18, 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};
    printMaxValPair1(v1,v1.size());
    return 0;
}

Đầu ra

6 3