นับคู่ (i,j) ที่ผลรวมคอลัมน์ j มากกว่าผลรวมแถว i ใน C++

ได้รับเมทริกซ์ N×N ต้องการนับคู่ดัชนี (i,j) ที่ผลรวมสมาชิกคอลัมน์ j มากกว่าผลรวมสมาชิกแถว i

ตัวอย่าง

matrix = {{1,2,0,1}, {3,3,0,2}, {1,3,0,2}, {3,0,0,2}};
Rowsum[0]=4, Colsum[0]=8
Rowsum[1]=8, Colsum[1]=8
Rowsum[2]=6, Colsum[2]=0
Rowsum[3]=5, Colsum[3]=7
คู่ที่ colsum[j] > rowsum[i]: (0,0),(0,1),(0,3),(2,0),(2,1),(2,3),(3,0),(3,1),(3,3) = 9 คู่

แนวทาง

• คำนวณ rowsum[i] และ colsum[j] โดยวนเมทริกซ์ครั้งเดียว
• ลูปซ้อน 2 ชั้นเปรียบเทียบ colsum[j] > rowsum[i] นับคู่ที่ตรงเงื่อนไข

ตัวอย่างโค้ด C++

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

int countPairs(int arr[][3], int n) {
    int count = 0;
    int rowsum[n] = {0};
    int 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];
        }
    }
    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 << endl << "Count of number of pairs: " << countPairs(Arr, side);
    return 0;
}

ผลลัพธ์

Count of number of pairs: 4