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

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

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

1	0	1
0	0	0
1	0	1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=0
tạo một mảng 2D sq có kích thước n x n
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - tăng sq [i mod n, j mod n] lên 1
Xác định một mảng v
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - chèn sq [i, j] vào cuối v
sắp xếp mảng v theo thứ tự ngược lại
để khởi tạo i:=0, j:=0, khi tôi
trả lại ret

Hãy cùng chúng tôi xem cách 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

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

Ví dụ

Đầu vào

Đầu ra