首页 > 试题广场 >

最小面积子矩阵

[编程题]最小面积子矩阵
  • 热度指数：5394 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）

输入描述:
每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K
接下来N行，每行M个数，表示矩阵每个元素的值


输出描述:
输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。
示例1

输入

4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出

1
算法知识视频讲解
开通博客
头像 nzxkc
发表于 2022-02-23 18:36:11
题目问题 找和>=K,包含元素最少的矩阵 思路 方法一 枚举左上角和右下角，O(n^4) 方法二（优化） 由于所有数值都是非负数，可以枚举上边界和下边界，然后确定上下边界之后枚举左右边界ij即可 要求包含元素最少的子矩阵（右边界固定的时候，左边界往右总和变小，面积也变小） j：最靠右且总和大于 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 philos
发表于 2021-03-03 20:33:26
思路 这一题还是有些复杂的，先说一下大致思路： 任选两列，把这两列间的元素相加成一列，即一维数组，实际宽度为 j - i + 1 遍历一维数组，找到和大于等于 K 的最短连续子序列，长度为 len 那么上面对应的子矩阵的面积为 (j - i + 1) * len 重复上述过程找到最小值 我们先来 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 粉詹眉
发表于 2024-03-23 22:54:16
#include <iostream> using namespace std; const int N=110; int a[N][N]; int f[N][N];//f[i][j]:从a[1][1]~a[i][j]的元素值之和 int main() { int n,m,k; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ooops!
发表于 2023-09-13 18:14:48
#include<bits/stdc++.h> using namespace std; int main(){ int n,m,k; while(cin>>n>>m>>k){ vector<vector< 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 KimKitsuragi
发表于 2024-03-06 11:30:47
#include <iostream> using namespace std; #define MAX 101 #define INF 0x7fffffff int sumOfMat(int i, int j, int width, int length, int(&arr)[ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 程昱同学
发表于 2023-01-25 13:18:45
#include <bits/stdc++.h> using namespace std; int m,n,k; int min_s=10001; int mp[100][100]; /*mp: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 粉詹眉
发表于 2024-02-28 17:24:40
#include <iostream> using namespace std; const int N=110; int a[N][N],f[N][N]; int main() { int n,m,k; cin>>n>>m>>k; 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 前缀和 双指针
难度：
29条回答 11807浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号