Tìm số cặp (x, y) trong mảng sao cho x^y > y^x trong C++

Giả sử chúng ta có hai mảng X và Y chứa các số nguyên dương. Hãy tìm số cặp (x, y) thỏa mãn x^y > y^x, trong đó x là phần tử của X và y là phần tử của Y. Ví dụ, với X = [2, 1, 6] và Y = [1, 5], kết quả là 3. Ba cặp thỏa mãn là (2, 1), (2, 5) và (6, 1).

Giải thuật hiệu quả

Chúng ta có thể giải quyết bài toán này một cách hiệu quả. Logic cốt lõi là: khi y > x thì x^y > y^x, ngoại trừ một số trường hợp đặc biệt. Dưới đây là các bước thực hiện:

• Sắp xếp mảng Y theo thứ tự tăng dần.
• Với mỗi phần tử x trong X, tìm chỉ số của phần tử nhỏ nhất trong Y mà lớn hơn x. Có thể sử dụng tìm kiếm nhị phân hoặc hàm upper_bound().
• Tất cả các phần tử sau chỉ số tìm được đều thỏa mãn điều kiện, cộng số lượng đó vào kết quả.
• Xử lý riêng các trường hợp ngoại lệ cho x = 0, 1, 2, 3.

Ví dụ minh họa

#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 << "Tổng số cặp: " << howManyPairs(X, Y, m, n);
    return 0;
}

Kết quả

Tổng số cặp: 3