简答题 偏难
#18321

黑白格 时间限制: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:python;toolbar:false">N = 110 w = [[0] * N for _ in range(N)] sum_w = [[0] * N for _ in range(N)] def main(): n, m, k = map(int, input().split()) for i in range(1, n+1): s = input() for j in range(1, m+1): w[i][j] = int(s[j-1]) sum_w[i][j] = sum_w[i][j-1] + w[i][j] ans = 0 for i in range(1, m+1): for j in range(i, m+1): num = [] now = 0 for l in range(1, n+1): tmp = sum_w[l][j] - sum_w[l][i-1] now += tmp num.append(now) if now &gt;= k: if ans == 0: ans = (j-i+1) * l else: ans = min(ans, (j-i+1) * l) L, R = 1, l while L &lt; R: mid = (L + R + 1) // 2 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)) print(ans) if __name__ == "__main__": main()</pre>
解析

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

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

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

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

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