简答题 偏难
#21131

黑白格 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。 小杨想知道至少包含k个黑色…

黑白格

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。

输入格式

第一行包含三个正整数n,m,k,含义如题面所示。

之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。

输出格式

输出一个整数,代表至少包含k个黑色格子的最小子矩形包含格子的数量,如果不存在则输出0。


输入样例

4 5 5
00000
01111
00011
00011

输出样例

6

样例解释

对于样例1,假设(i,j) 代表第i 行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为(2,4),(2,5),(4,4),(4,5),共包含6个格子。

数据范围

对于全部数据,保证有1≤n,m≤100,1≤k≤n×m。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 110; int w[N][N]; int sum[N][N]; int n,m; int main(){ int k; cin&gt;&gt;n&gt;&gt;m&gt;&gt;k; for(int i=1;i&lt;=n;i++){ string s; cin&gt;&gt;s; for(int j=1;j&lt;=m;j++){ w[i][j]=s[j-1]-'0'; sum[i][j]=sum[i][j-1]+w[i][j]; } } int ans = 0; for(int i=1;i&lt;=m;i++){ for(int j=i;j&lt;=m;j++){ vector&lt;int&gt; num; int now = 0; for(int l=1;l&lt;=n;l++){ int tmp = sum[l][j]-sum[l][i-1]; now+=tmp; num.push_back(now); if(now&gt;=k){ if(ans ==0)ans=(j-i+1)*l; else ans=min(ans,(j-i+1)*l); int L=1,R=l; while (L &lt; R){ int mid = L + R + 1 &gt;&gt; 1; if (now-num[mid-1]&gt;=k) L = mid; else R = mid - 1; } if(now-num[L-1]&gt;=k){ if(ans ==0)ans=(j-i+1)*(l-L); else ans=min(ans,(j-i+1)*(l-L)); } } } } } cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析

1.二维数组存储对应格子颜色的值

2.使用前缀和的技巧来快速计算任意子矩形内的格子数量。这样一来,不需要重复遍历每个可能的子矩形来计算其中的黑色格子数,从而节省时间

3.通过检查每个可能的子矩形,计算其中的黑色格子数量。找到一个最小的子矩形,使得其中至少有 k 个黑色格子。

4.使用二分查找的技巧,在内部循环中快速定位满足条件的子矩形大小

5.最后,我们输出这个最小子矩形的面积。如果不存在满足条件的子矩形,则输出0