양의 정수로 구성된 두 개의 배열 X와 Y가 있다고 가정합니다. x^y> y^x와 같은 쌍의 수를 찾으십시오. 여기서 x는 X의 요소이고 y는 Y의 요소입니다. X =[2, 1, 6] 및 Y =[1, 5]라고 가정합니다. , 출력은 3이 됩니다. 세 쌍이 있으므로 (2, 1), (2, 5) 및 (6, 1)
효율적인 방법으로 해결할 수 있습니다. 논리는 간단합니다. 몇 가지 예외를 제외하고는 y> x 다음 x^y> y^x일 것입니다. 이것이 트릭입니다.
-
배열 Y
정렬 -
X의 각 요소 x에 대해 Y의 x보다 큰 가장 작은 숫자의 인덱스를 찾아야 합니다. 이를 위해 이진 검색을 사용합니다. 그렇지 않으면 upper_bound() 함수도 사용할 수 있습니다.
-
찾은 인덱스 이후의 모든 숫자는 관계를 만족하므로 카운트에 추가하기만 하면 됩니다.
예시
#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
if (x == 0)
return 0;
if (x == 1)
return no_of_y[0];
int* index = upper_bound(Y, Y + n, x);
int ans = (Y + n) - index;
ans += (no_of_y[0] + no_of_y[1]);
if (x == 2)
ans -= (no_of_y[3] + no_of_y[4]);
if (x == 3)
ans += no_of_y[2];
return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
int no_of_y[5] = {0};
for (int i = 0; i < n; i++)
if (Y[i] < 5)
no_of_y[Y[i]]++;
sort(Y, Y + n);
int total_pairs = 0;
for (int i=0; i< m; i++)
total_pairs += count(X[i], Y, n, no_of_y);
return total_pairs;
}
int main() {
int X[] = {2, 1, 6};
int Y[] = {1, 5};
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
cout << "Total pair count: " << howManyPairs(X, Y, m, n);
} 출력
Total pair count: 3