Range Addition II trong C++

Giả sử chúng ta có một ma trận M kích thước m x n được khởi tạo toàn giá trị 0, cùng với một số phép cập nhật. Các phép toán được biểu diễn bằng mảng 2D, trong đó mỗi phép toán là một mảng chứa hai số nguyên dương x và y, nghĩa là M[i][j] sẽ được tăng thêm 1 với mọi i trong khoảng 0 đến x-1 và mọi j trong khoảng 0 đến y-1. Ta cần tìm số lượng phần tử có giá trị lớn nhất trong ma trận sau khi thực hiện tất cả các phép toán.

Ví dụ: với m = 3, n = 3 và operations = [[2,2],[3,3]], kết quả sẽ là 4.

Ma trận ban đầu

Sau phép toán [2,2]

Sau phép toán [3,3]

Giải thuật

Để giải bài toán này, ta nhận thấy rằng các ô bị ảnh hưởng bởi tất cả các phép toán chính là giao của các vùng cập nhật. Do đó, kích thước vùng giao chính là min(x) × min(y) của tất cả các phép toán.

1. Khởi tạo minR = m, minC = n.
2. Duyệt qua từng phép toán op trong mảng ops:
   • Cập nhật minR = min(minR, op[0]).
   • Cập nhật minC = min(minC, op[1]).
3. Kết quả là minR * minC.

Ví dụ triển khai C++

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

class Solution {
public:
    int maxCount(int m, int n, const vector<vector<int>>& ops) {
        int minR = m;
        int minC = n;
        for (const auto& op : ops) {
            minR = min(minR, op[0]);
            minC = min(minC, op[1]);
        }
        return minR * minC;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{2,2},{3,3}};
    cout << ob.maxCount(3, 3, v); // Kết quả: 4
    return 0;
}

Đầu vào / Đầu ra

Input: 3, 3, {{2,2},{3,3}}
Output: 4