对于给定的n个正整数数组arr [],任务是从数组中确定元素arr [i]和arr [j],以使arr [i] Carr [j]最有可能。对于多于1有效对,请打印其中任何一个。
输入项
arr[] = {4, 1, 2}
输出结果
4 24C1 = 44C2 = 42C1 = 4 (4, 2) is the only pairs with maximum nCr.
n C r被视为单调递增函数,即n + 1 C r > n C r。我们可以运用这一事实来接近我们的答案;我们将在所有给定的整数中选择最大值n。这样我们固定了n的值。
现在,我们专注于r。我们知道n C r = n C n-r,这表明nCr将首先达到其最大值,然后减小。
对于n的奇数值,则我们的最大值将出现在n / 2和n / 2 + 1处。
关于n = 11,我们将获得11 C 5和11 C 6的最大值。
对于n的偶数,则我们的最大值将出现在n / 2处。
关于n = 4,我们将获得4 C2时的最大值
// This is C++ implementation of the approach #include <bits/stdc++.h> using namespace std; //现在可以打印出最大nCr的线对 void printMaxValPair1(vector<long long>& v1, int n1){ sort(v1.begin(), v1.end()); //这提供了nCr中的N值 long long N1 = v1[n1 - 1]; //情况1:当N1为奇数时 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; } //情况2:当N1是偶数时 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