Số lượng 1 tối đa trong C++

Giả sử chúng ta có ma trận M kích thước w x h, sao cho mỗi ô có giá trị 0 hoặc 1, và bất kỳ ma trận con vuông nào của M kích thước l x l có tối đa maxOnes số 1. Chúng ta phải tìm số 1 tối đa có thể mà ma trận M có thể có.

Vì vậy, nếu đầu vào là w = 3, h = 3, l = 2, maxOnes = 1, đầu ra sẽ là 4 vì trong ma trận 3*3, không ma trận con 2*2 nào có hơn 1 số 1. Giải pháp tốt nhất có 4 số 1 là:

Để giải quyết, chúng ta sẽ làm theo các bước:

• ret := 0

• Tạo mảng 2D sq kích thước n x n

• Khởi tạo i := 0, khi i < height, cập nhật (tăng i lên 1), làm:

  • Khởi tạo j := 0, khi j < width, cập nhật (tăng j lên 1), làm:

    • Tăng sq[i mod n, j mod n] lên 1

• Định nghĩa mảng v

• Khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), làm:

  • Khởi tạo j := 0, khi j < n, cập nhật (tăng j lên 1), làm:

    • Chèn sq[i, j] vào cuối v

• Sắp xếp mảng v theo thứ tự ngược

• Khởi tạo i := 0, j := 0, khi i < kích thước v và j < maxOnes, cập nhật (tăng i lên 1), (tăng j lên 1), làm:

• Trả về ret

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {       int ret = 0;       vector < vector <int> > sq(n, vector <int>(n));       for(int i = 0; i < height; i++){          for(int j = 0; j < width; j++){             sq[i % n][j % n]++;          }       }       vector <int> v;       for(int i = 0; i < n; i++){          for(int j = 0; j < n ; j++){             v.push_back(sq[i][j]);          }       }       sort(v.rbegin(), v.rend());       for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){          ret += v[i];       }       return ret;    } }; main(){    Solution ob;    cout << (ob.maximumNumberOfOnes(3,3,2,1)); }

Đầu vào

3, 3, 2, 1

Đầu ra

4