刷题记录:牛客NC24622Brownie Slicing

传送门:牛客

输入:
5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1
输出:
3 

牛客网上的两星题,洛谷上评级为蓝,个人感觉牛客网上难度评价低了,感觉应该是三星差不多,光光这个二维的前缀和感觉就是比较难想的

主要思路:

1. 首先肯定是判断出这道题应该使用二分答案来做,然后我们只要判断对于我们二分出的每一个答案是不是符合我们的要求即可,所以我们只需要check函数即可
2. 在我们千万不要将题目看错,每一块蛋糕都是要切成B-1块的,而不是总共切B-1刀,当时我看错题目然后浪费了很多时间.其次我们发现横着切是一切到底的,所以我们可以试着枚举横着切的条数然后在枚举竖着切的位置,那么该怎么确定要不要增加这一块切的,就是判断当前范围内的切B-1块是不是都符合即可,如果不符合意味着我们肯定是要加大巧克力的竖着的行数的要增加.并且我们还需要记录每一切的位置,包括横与竖
3. 现在摆在我们面前的问题就是如何快速的计算我们切一刀所在的一大块巧克力中的巧克力数量了,这时我们就要引出今天的主题了(二维前缀和),首先假设我们的巧克力大块永远都是一行的话,显然此时我们就会想到前缀和来直接求出我们每一部分的巧克力数量,但是当我们的行数并不是一格的时候怎么办呢,此时我们就不能直接保存每一格的巧克力数量了,此时我们需要保存二维的前缀和
   请看下面的样例

1    1    1
2    2    2
3    3    3
我们使用sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]来计算从左上角的(1,1)开始一直到(i,j)这个点构成的矩阵的总和
为什么这个式子是正确的呢,首先我们会发现sum[i][j-1]存的是(1,1)->(i,j-1)的矩阵的总和
sum[i-1][j]存的是(1,1)->(i-1,j)的矩阵的总和
j-1 j   j+1
?   ?   ?       i-2
?   ?   ?       i-1
?   ?   ?        i
显然我们经过手模就会发现这个结论是正确的
然后怎么求出每一块我们切割出来的巧克力块的值呢,我们只要用我们的大的矩阵和来减去当前块中我们已经被切掉的矩阵和即可

就如上图,记住此时我们存的是从最左端到目前点的矩阵和,所以我们需要补上多减去的一块

假设 l_hang代表上一次横着切的地方(也就是红线),l_lie代表上一次竖着切的地方,此时我们需要求的黑色部位的方法就是:sum[i][j]-sum[i][l_lie]-sum[l_hang][j]+sum[l_hang][l_lie]

弄懂这些之后我们的问题也就迎刃而解了

下面是具体代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
int r,c;int a,b;
int cake[600][600];
int sum[600][600];
int check(int mid) {
	int l_hang=0;int l_lie=0;int num_hang=0;int num_lie=0;
	for(int i=1;i<=r;i++) {
		l_lie=0;num_lie=0;
		for(int j=1;j<=c;j++) {
			if(d>=mid) {
				l_lie=j;num_lie++;
			}
		}
		if(num_lie>=b) {
			l_hang=i;
			num_hang++;
		}
	}
	if(num_hang>=a) return true;
	else return false;
}
int main() {
	memset(cake,0,sizeof(cake));
	memset(sum,0,sizeof(sum));
	r=read();c=read();a=read();b=read();
	int Le=0,Re=0;
	for(int i=1;i<=r;i++) {
		for(int j=1;j<=c;j++) {
			cake[i][j]=read();
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+cake[i][j];
			Re+=cake[i][j];
		}
	}
	Re/=(a+b);
	int ans=0;
	while(Le<=Re){
		int mid=(Le+Re)>>1;
		if(check(mid)) {
			ans=mid;
			Le=mid+1;
		}else {
			Re=mid-1;
		}

	}
	cout<<ans<<endl;
	return 0;	
}