Khái niệm
Đối với một mảng arr [] đã cho gồm n số nguyên dương, nhiệm vụ là xác định các phần tử arr [i] và arr [j] từ mảng sao cho arr [i] Carr [j] nhiều nhất có thể. Đối với nhiều hơn 1 cặp hợp lệ, hãy in bất kỳ cặp nào trong số đó.
Đầu vào
arr[] = {4, 1, 2} Đầu ra
4 2 4C1 = 4 4C2 = 4 2C1 = 4 (4, 2) is the only pairs with maximum nCr.
Phương pháp
n C r được coi như một hàm tăng đơn điệu, đó là n + 1 C r > n C r . Chúng ta có thể áp dụng thực tế này để đi gần câu trả lời của mình; chúng ta sẽ chọn n max trong số tất cả các số nguyên đã cho. Bằng cách này, chúng tôi đã cố định giá trị của n.
Bây giờ, chúng tôi tập trung cho r. Như chúng ta biết rằng n C r = n C n-r , nó cho biết nCr trước tiên sẽ đạt cực đại và sau đó giảm.
Đối với giá trị lẻ của n, thì cực đại của chúng ta sẽ xảy ra ở n / 2 và n / 2 + 1.
Đối với n =11, chúng ta sẽ nhận được điểm cực đại ở 11 C 5 và 11 C 6 .
Đối với giá trị chẵn của n, thì cực đại của chúng ta sẽ xảy ra ở n / 2.
Đối với n =4, chúng ta sẽ nhận được điểm cực đại ở 4 C2
Ví dụ
// This is C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Now Function to print the pair that gives maximum nCr
void printMaxValPair1(vector<long long>& v1, int n1){
sort(v1.begin(), v1.end());
// This provides the value of N in nCr
long long N1 = v1[n1 - 1];
// Case 1 : When N1 is odd
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;
}
// Case 2 : When N1 is even
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;
}
}
// Driver code
int main(){
vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
int n1 = v1.size();
printMaxValPair1(v1, n1);
return 0;
} Đầu ra
6 3