题意是 求最小的矩形覆盖面积内包含 k 个 空位置
枚举上下边界然后 双端队列 求 最小面积
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
using namespace std;
typedef long long ll;
const double ESP = 10e-;
const int MOD = +;
const int MAXN = +;
char graph[MAXN][MAXN];
int sum[MAXN][MAXN]; int main(){
// freopen("input.txt","r",stdin);
int R,C,K;
while(scanf("%d%d%d",&R,&C,&K)){
if(!R && !C && !K){
break;
}
for(int i = ;i < R;i++){
scanf("%s",graph[i]);
}
memset(sum,,sizeof(sum));
for(int i = ;i <= R;i++){
for(int j = ;j <= C;j++){
sum[i][j] = sum[i][j-];
sum[i][j] += sum[i-][j] - sum[i-][j-];
if(graph[i-][j-] == '.'){
sum[i][j]++;
}
}
}
int ans = R * C;
for(int x2 = R;x2 > ;x2--){
if(sum[x2][C] < K){
break;
}
for(int x1 = ;x1 <= R;x1++){
if(sum[x2][C] - sum[x1-][C] < K){
break;
}
int y1 = ;
int y2 = ;
while(y1 <= C && y2 <= C){
int cnt = sum[x2][y2]-sum[x1-][y2]-
(sum[x2][y1-] - sum[x1-][y1-]);
if(cnt < K){
y2++;
}else{
ans = min(ans,(x2-x1+)*(y2-y1+));
y1++;
if(y1 > y2){
break;
}
}
}
}
}
printf("%d\n",ans);
}
return ;
}
跟上面是类似的题，今年省赛的题 T_T
求最小矩形面积覆盖的 星星数 至少 为 k 个
就跟上面一样的题型了23333
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
using namespace std;
typedef long long ll;
const double ESP = 10e-;
const int MOD = +;
const int MAXN = +;
int graph[MAXN][MAXN];
int sum[MAXN][MAXN];
int main(){
//freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d%d",&n,&k);
memset(graph,,sizeof(graph));
memset(sum,,sizeof(sum));
int stX = ,edX = ,stY = ,edY = ;
while(n--){
int a,b;
scanf("%d%d",&a,&b);
graph[a][b]++;
stX = min(a,stX);
stY = min(b,stY);
edX = max(a,edX);
edY = max(b,edY);
}
for(int i = stX;i <= edX;i++){
for(int j = stY;j <= edY;j++){
sum[i][j] = sum[i-][j] + sum[i][j-] - sum[i-][j-];
sum[i][j] += graph[i][j];
}
} int ans = (edX-stX+)*(edY-stY+);
for(int x2 = edX;x2 >= stX;x2--){
if(sum[x2][edY] < k){
break;
}
for(int x1 = stX;x1 <= edX;x1++){
if(sum[x2][edY] - sum[x1-][edY] < k){
break;
}
int y1 = stY;
int y2 = stY;
while(y1 <= edY && y2 <= edY){
int cnt = sum[x2][y2] - sum[x2][y1-]-(sum[x1-][y2]-sum[x1-][y1-]);
if(cnt < k){
y2++;
}else{
ans = min(ans,(x2-x1+)*(y2-y1+));
y1++;
if(y1 > y2){
break;
}
}
}
}
}
printf("%d\n",ans);
}
return ;
}