개념
n개의 양의 정수로 구성된 배열 arr[]과 관련하여 작업은 배열에서 요소 arr[i]와 arr[j]를 결정하여 arr[i]Carr[j]가 최대 가능하도록 하는 것입니다. 1개 이상의 유효한 쌍과 관련하여 그 중 하나를 인쇄하십시오.
입력
arr[] = {4, 1, 2}
출력
4 2 4C1 = 4 4C2 = 4 2C1 = 4 (4, 2) is the only pairs with maximum nCr.
방법
n Cr 단조 증가 함수, 즉 n+1 으로 처리됩니다. Cr> n Cr . 우리는 이 사실을 적용하여 우리의 답에 가까워질 수 있습니다. 주어진 모든 정수 중에서 최대 n을 선택합니다. 이런 식으로 n의 값을 고정했습니다.
이제 r에 집중합니다. n Cr = n Cn-r , nCr이 먼저 최대값에 도달한 다음 감소함을 나타냅니다.
n의 홀수 값에 대해 최대값은 n / 2 및 n / 2 + 1에서 발생합니다.
n =11과 관련하여 11 에서 최대값을 얻습니다. C5 그리고 11 C6 .
n의 짝수 값에 대해 최대값은 n / 2에서 발생합니다.
n =4와 관련하여 4 에서 최대값을 얻습니다. C2
예시
// 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; }
출력
6 3