luoguP3017Brownie Slicing
2024-08-28 04:44:11
https://www.luogu.org/problem/P3017
题意
给你一个蛋糕,R行C列 ,每个点有巧克力碎屑(如下)
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
你要先横着切a-1刀,将蛋糕分为a块,然后对于每一块,分别竖着切b-1刀
将整个蛋糕分成a*b块,求巧克力屑最少的一块最多有多少屑
R,C≤500 N_ij≤4,000
A ≤ R , B ≤ C
分析
依旧是最多的 最少值 是多少(有点绕口
依旧满足二分性
依旧可以合理的check
(请自主思考
我们这里注意的是怎么check(k)
思路:按照题目说的,先横着切一块,然后再切出的一块内竖着合理地切成b块,如果不能合法切成b块,就把第一刀横着的往下挪,直到能够切成b块,最后判断横着切的次数是否合法,得出k是否合法。
优化: 二维前缀和(很容易想到吧...不解释了
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 500+9
int R, C, a, b;
int arr, tmp[MAX*MAX], cnt;
int s[MAX][MAX]; //前缀和
int check(int k) {//最小的巧克力屑
int cuta = 0, now = 0;//目前切了几条 , 上一条在哪里
for(int i = 1; i <= R; i++) {
int cutb = 0, last = 0;//当前切了几块, 切的上一块在哪里
for(int j = 1; j <= C; j++)
if(s[i][j] - s[now][j] - s[i][last] + s[now][last] >= k) cutb++, last = j;//建议画图看看
if(cutb >= b) {
cuta++;
now = i;
}
}
return cuta >= a;
/*关于为什么这是>=: 我们这的if的意思是,只要当前块的和>=k,我们就切,
所以可能多切几刀,但这并不影响正确性: 你把后面多出来的几刀去掉,也只是使最后一块或最后一行额外的大,所以仍然合法 */
}
int main() {
scanf("%d%d%d%d",&R, &C, &a, &b);
for(int i = 1; i <= R; i++)
for(int j = 1; j <= C; j++) {
scanf("%d", &arr);
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr;
}
int l = 1,r = s[R][C], mid;
int ans = 0;
while(l <= r) {//让ans最大
mid = (l+r)>>1;
if(check(mid)) {
ans = mid;
l = mid+1;
} else {
r = mid-1;
}
}
printf("%d",ans);
}
最新文章
- 关于bootstrap的一些运用
- jQuery操作控件
- android 小方法
- android 使用NinePatch图作Background,导致布局混乱
- Scala中的语言特性是如何实现的(3) -- Trait
- 洛谷 P1359 租用游艇
- Apache localhost和局域网ip地址访问
- Python实现浏览器自动化操作
- 解决com.fasterxml.jackson.databind.JsonMappingException: No suitable
- opencv debug版本在linux下编译,并写了一个DEMO
- 批量修改mac系统文件的可读写权限
- day16 python之匿名函数,递归函数
- 012-docker-安装-fabric:1.4
- 常见的移动端Web页面问题
- 数据结构(C语言版)-第7章 查找
- Axel and Marston in Bitland CodeForces - 782F (bitset优化)
- eml文件解析实例,简历信息抓取工具
- openssl asn.1 生成DER文件,把DER文件转换成内部数据结构
- [转]ggplot2用法简单介绍
- Opengl创建几何实体——四棱锥和立方体
热门文章
- mssql sqlserver 将逗号分隔的一列数据转换为多列数据的方法分享
- bootrom/spl/uboot/linux逐级加载是如何实现的?
- 以太网驱动的流程浅析(二)-Ifconfig的详细代码流程【原创】
- Vue入门(二)
- plsql查询数据显示为乱码解决方案
- Python变量与内存管理
- python 各层级目录下的import方法
- Python必备收藏!博士大佬总结的Pycharm 常用快捷键思维导图
- pixijs shader fade 从左到有右淡入 从下到上淡入效果
- [06]ASP.NET Core中的进程内(InProcess)托管