Đếm bộ ba (a,b,c) từ 3 mảng thỏa A[i] < B[j] < C[k] C++

Cho 3 mảng A, B, C cùng kích thước N. Đếm số bộ ba (i,j,k) sao cho A[i] < B[j] < C[k].

Ví dụ minh họa

Ví dụ 1:

• Input: A={1,4,5}, B={0,2,3}, C={0,6,7}
• Output: 4
• Giải thích: (1,2,6), (1,2,7), (1,3,6), (1,3,7).

Ví dụ 2:

• Input: A={7,8,9}, B={4,5,6}, C={1,2,3}
• Output: 0

Mã nguồn C++ (Vét cạn O(n³))

#include <bits/stdc++.h>
using namespace std;

int countTriplets(int a[], int b[], int c[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (a[i] < b[j] && b[j] < c[k]) count++;
            }
        }
    }
    return count;
}

int main() {
    int A[] = {1, 2, 3};
    int B[] = {2, 3, 2};
    int C[] = {4, 3, 1};
    int N = 3;
    cout << "So bo ba: " << countTriplets(A, B, C, N);
    return 0;
}

Kết quả chạy chương trình

So bo ba: 6

Tối ưu hóa O(n log n) - Sắp xếp + Binary Search

Sắp xếp 3 mảng. Với mỗi B[j], đếm số A[i] < B[j] và số C[k] > B[j].

#include <bits/stdc++.h>
using namespace std;

long long countTripletsOptimized(vector A, vector B, vector C) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    long long count = 0;
    for (int b : B) {
        long long cntA = lower_bound(A.begin(), A.end(), b) - A.begin();
        long long cntC = C.end() - upper_bound(C.begin(), C.end(), b);
        count += cntA * cntC;
    }
    return count;
}

Độ phức tạp

Lưu ý

• Sắp xếp không làm thay đổi số lượng bộ ba thỏa mãn vì điều kiện chỉ so sánh giá trị.
• lower_bound: vị trí đầu tiên ≥ b → số phần tử < b.
• upper_bound: vị trí đầu tiên > b → số phần tử > b.