大家好 我是寸铁💪
考前需要刷大量真题,大家一起相互监督，每日做N题，一起上岸吧✌️ ~
第一期(二)
题目：分巧克力 ✨
考点：二分 💪
该题目类型会同时收录在相关复习专题，供大家学习
收录👇
蓝桥杯上岸必背！！！(持续更新中~)
不清楚蓝桥杯考什么的点点下方👇
考点秘籍
想背纯享模版的伙伴们点点下方👇
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全（第二期）
想背注释模版的伙伴们点点下方👇
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)！！！
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句（期末冲刺）
想看JavaB组填空题的伙伴们点点下方 👇
填空题
二分
二分出答案！
怎么二分出答案？
这道题我们可以得出的是二分的结果是满足k块巧克力的最大边长是多少？
题目要求：
1.形状是正方形，边长是整数
2.大小相同
即要求边长均为x
我们就可以确保得到边长一致的正方形
大小相同即分出的块数为整数，向下取整！！！
得到能够凑出的整块巧克力
如果分出的块数有小数的大小肯定不同。
长、宽分别为H、W
块数：(H/x)*(W/x)
为什么是这么多块？
相同的x下
我们可以发现长为H
可以被切成H/x块
我们可以发现宽为W
可以被切成W/x块
这么多块的组合起来为(H/x)*(W/x)这么多块
那我们推出这个公式后，我们怎么利用二分来处理这道题？
我们知道二分一般情况下需要具有二段性/单调性
即确定一个mid后，两边是否具有二段性/单调性
假设k=(H/x)*(W/x)
我们根据公式发现(H/x)*(W/x)中H、W是常量。x是变量,且随着x的增大,k值是越来越小的。
而随着x的减小,k值是越来越大的。
中间必定存在k使得x最大
这即是我们需要的二段性。
画出图形应该是单调递减的曲线
x是我们要二分的答案
更进一步我们可以发现
假设我们在x的条件下刚好二分出k块的巧克力。
由上证明,比x小的也一定满足可以条件,可以分出大于k块巧克力。
我们让l右移让他往右边去找,k块巧克力下边长尽可能的大
即l=mid;
比x大的一定不满足条件，不足以分出k块巧克力。
我们让r左移让他往左边去找,k块巧克力下边长尽可能的大
即r=mid-1;文章来源：https://www.toymoban.com/news/detail-579504.html
二分出的k块巧克力下的x必定是满足k块的最大边长！！！
Accode
import java.util.*;
public class Main{
static int N=100010;
static int cake[][]=new int[N][2];
//输入是N行2列
//不要开N行N列用不到的空间会MLE
static int n,m,k;
public static void main(String []args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
k=sc.nextInt();
for(int i=0;i<n;i++){
cake[i][0]=sc.nextInt();
cake[i][1]=sc.nextInt();
}
//答案确保所得至少1*1
//边长最小为1
//二分的左边界为1
//右边界为最大边长1e5
int l=1;
int r=(int)1e5;
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
//mid下的块>=k则l右移l=mid
//注意mid是满足>=k所以是l=mid
//与之对应的是r=mid-1
//因为此时check(mid)<k
//所以需要往左移且mid不满足条件
//所以r=mid-1
else r=mid-1;
}
System.out.println(l);
}
public static boolean check(int m){
int res=0;
for(int i=0;i<n;i++){
res+=(cake[i][0]/m)*(cake[i][1]/m);
//统计能分出的块数
}
//块数>=k说明是需要将边长边大块数减少
//即l=mid;
if(res>=k)return true;
//反之则说明不足k块需要将边长减小块数增大
//即r=mid-1
return false;
}
}
☀️☀️☀️☀️☀️☀️
后续有补充，持续更新中🌋
喜欢的伙伴点点赞，关个注💗文章来源地址https://www.toymoban.com/news/detail-579504.html
到了这里，关于蓝桥杯上岸每日N题第一期(二)！！！的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[职场] 会计学专业学什么 #其他#知识分享#职场发展](https://imgs.yssmx.com/Uploads/2024/02/830441-1.jpeg)
