大家好 我是寸铁
考前需要刷大量真题,大家一起相互监督,每日做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;
二分出的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 cake[i][0]=sc.nextInt(); cake[i][1]=sc.nextInt(); } //答案确保所得至少1*1 //边长最小为1 //二分的左边界为1 //右边界为最大边长1e5 int l=1; int r=(int)1e5; while(l 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) //所以需要往左移且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 res+=(cake[i][0]/m)*(cake[i][1]/m); //统计能分出的块数 } //块数>=k说明是需要将边长边大块数减少 //即l=mid; if(res>=k)return true; //反之则说明不足k块需要将边长减小块数增大 //即r=mid-1 return false; } } ☀️☀️☀️☀️☀️☀️ 后续有补充,持续更新中 喜欢的伙伴点点赞,关个注 推荐阅读
发表评论