P3017 [USACO11MAR]Brownie Slicing G 题解

题意简述

给定一个 $r \times c$ 矩阵，先水平切成 $a$ 块，然后每块竖着切成 $b$ 块，让每块的的值 $a_{ij}$ 的最大值最小。

但这里有个坑点注意一下：并不是每一刀都是水平或垂直的。

解题思路

比较容易可以想到二分答案。

所谓二分答案，就是用二分的方法，在可能的答案区间里找出问题的方法。

当然，纯粹的二分答案肯定会 TLE，因为对每块的枚举时间复杂度就有平方级别。

所以这里可以采用二维数组前缀和来优化，每次判断时间复杂度可以到 $Θ(1)$。

代码实现

#include<bits/stdc++.h>
using namespace std;
int pre[1005][1005],maps[1005][1005];
int lef,rig,n,m,a,b,ans;
int pre_sol(int i,int j) {
	int tmp=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+maps[i][j];
	return tmp;
}
int pre_spl(int i,int j,int mem_i,int mem_j) {
	int tmp=pre[i][j]-pre[i][mem_j]-pre[mem_i][j]+pre[mem_i][mem_j];
	return tmp;
}
bool check(int t) {
	int sum=0,num=0,mem_i=0,mem_j=0;
	for(int i=1;i<=n;i++) {
		mem_j=0; num=0;
		for(int j=1;j<=m;j++) {
			if(pre_spl(i,j,mem_i,mem_j)>=t) {
				num++; mem_j=j;
			}
		}
		if(num>=b) {
			sum++; mem_i=i;
		}
	}
	if(sum>=a) return true;
	else return false;
}
int main() {
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&maps[i][j]);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) pre[i][j]=pre_sol(i,j);
	rig=pre[n][m]/(a*b);
	while(lef<=rig) {
		int mid=(lef+rig)/2;
		if(check(mid)) {ans=mid; lef=mid+1;}
		else rig=mid-1;
	}
	printf("%d",ans);
	return 0;
}
//code by TheCedar