A32251. 黑白格题面描述小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
填空题
困难
知识点
题目描述
黑白格
题面描述
小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数 n，m，k，含义如题面所示。
之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。
输出格式
输出一个整数，代表至少包含k个黑色格子的最小子矩形包含格子的数量，如果不存在则输0。
样例1
输入
4 5 5
00000
01111
00011
00011
输出
6
样例解释
对于样例1，假设(i,j) 代表第i行第k列，至少包含5个黑色格子的最小子矩形的四个顶点为 (2,4)，(2,5)，(4,4)，(4,5)，共包含6个格子。
数据范围
对于全部数据，保证有 1 ≤ n,m ≤ 100, 1 ≤ k ≤ n * m 。
参考答案
#include<bits/stdc++.h> using namespace std; const int N = 110;
int w[N][N];
int sum[N][N];
int n,m;
int main() {
int k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++) {
string s;
cin>>s;
for(int j=1; j<=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<=m; i++) {
for(int j=i; j<=m; j++) {
vector<int> num;
int now = 0;
for(int l=1; l<=n; l++) {
int tmp = sum[l][j]-sum[l][i-1];
now+=tmp;
num.push_back(now);
if(now>=k) {
if(ans ==0)ans=(j-i+1)*l;
else ans=min(ans,(j-i+1)*l);
int L=1,R=l;
while (L < R) {
int mid = L + R + 1 >> 1;
if (now-num[mid-1]>=k) L = mid;
else R = mid - 1;
}
if(now-num[L-1]>=k) {
if(ans ==0)ans=(j-i+1)*(l-L);
else ans=min(ans,(j-i+1)*(l-L));
}
}
}
}
}
cout<<ans<<"\n";
}
上一题
下一题