在 C++ 中根据给定约束条件求解 N*N 矩阵中 1 的最大个数

任务是找到在满足以下约束条件下，二进制矩阵中可能的 1 的最大个数。

给定两个整数 N 和 X，其中 X<=N。二进制矩阵的大小应为 N*N，并且每个大小为 X*X 的子矩阵都应至少包含一个零。

让我们用一个例子来理解我们必须做什么：

输入 - N=4，X=2

输出 - 12

说明 - 结果矩阵将是：

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

输入 - N=7，X=3

输出 - 45

下面程序中使用的方法如下：

• 为了获得 1 的最大个数，我们首先必须找到矩阵中所需的零的最小个数。

  通过观察所有矩阵中的共同模式，可以看出所需的零的个数 = (N / X)²

  因此，1 的最大个数 = 矩阵中的元素总数 - 零的个数

• 在 MaxOne() 函数中，创建一个 int 类型的变量 Z，并将所需的零的最小个数 (N / X)² 存储在其中。

• 然后初始化另一个 int 类型的变量 total = N*N 来存储矩阵的总大小。

• 最后，初始化 int ans = total – Z 来存储最终答案并返回 ans。

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X){
   // Minimum number of zeroes that are needed
   int Z = (N / X);
   Z = Z * Z;
   /* Totol elements in matrix = square of the size of the matrices*/
   int total =N * N;
   //Final answer
   int ans = total - Z;
   return ans;
}
int main(){
   int N = 4;
   int X = 2;
   cout << MaxOne(N, X);
   return 0;
}

输出

如果我们运行上面的代码，我们将得到以下输出：

12

Sunidhi Bansal

更新于：2020年8月17日

91 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习