Đếm cặp chỉ số (i,j) có tổng cột j lớn hơn tổng hàng i trong ma trận C++

Cho ma trận vuông N×N. Đếm số cặp chỉ số (i,j) sao cho tổng các phần tử của cột j lớn hơn tổng các phần tử của hàng i.

Ví dụ minh họa

Input:

matrix = {
    {1, 2, 0, 1},
    {3, 3, 0, 2},
    {1, 3, 0, 2},
    {3, 0, 0, 2}
}

Output: 9

Giải thích:

• Row sums: [4, 8, 6, 5]
• Col sums: [8, 8, 0, 7]
• Cặp (i,j) thỏa rowsum[i] < colsum[j]: (0,0),(0,1),(0,3),(2,0),(2,1),(2,3),(3,0),(3,1),(3,3) = 9 cặp

Mã nguồn C++

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

int countPairs(int arr[][3], int n) {
    int count = 0;
    int rowsum[100] = {0};
    int colsum[100] = {0};
    
    // Tính tổng hàng và cột
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rowsum[i] += arr[i][j];
            colsum[j] += arr[i][j];
        }
    }
    
    // Đếm cặp thỏa mãn
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (colsum[j] > rowsum[i]) count++;
        }
    }
    return count;
}

int main() {
    int Arr[][3] = {{1,3,5}, {2,4,6}, {3,5,7}};
    int side = 3;
    cout << "So cap (i,j) co tong cot > tong hang: " << countPairs(Arr, side);
    return 0;
}

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

So cap (i,j) co tong cot > tong hang: 4

Độ phức tạp

• Thời gian: O(N²) - tính tổng + đếm cặp.
• Không gian: O(N) - mảng rowsum, colsum.

Tối ưu hóa đếm cặp O(N log N)

Sau khi có rowsum[] và colsum[], sắp xếp colsum[]. Với mỗi rowsum[i], dùng binary search tìm số phần tử trong colsum[] lớn hơn nó.

int countPairsOptimized(int arr[][100], int n) {
    vector rowsum(n, 0), colsum(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            rowsum[i] += arr[i][j];
            colsum[j] += arr[i][j];
        }
    sort(colsum.begin(), colsum.end());
    
    long long count = 0;
    for (int i = 0; i < n; i++) {
        // Số phần tử trong colsum > rowsum[i]
        auto it = upper_bound(colsum.begin(), colsum.end(), rowsum[i]);
        count += colsum.end() - it;
    }
    return count;
}