题目2.分巧克力 - 蓝桥云课 (lanqiao.cn)二分必须得是有序的二分是不断把有序的查找区间缩小为原来的一半直到找到目标元素或确定目标元素不存在思路本题是二分答案经典题直接求最大边长很难反过来给定边长mid判断能不能切出至少 K 块这个判断函数check很好写。二分枚举边长找满足条件的最大边长。是最大化答案边长越大能切出来的巧克力块数越少具有单调性所以可以二分答案。如果mid边长可以分出≥k 块说明答案≥mid继续往更大的尝试如果mid不够 k 块说明答案一定 mid只能往更小尝试最新的题解复习这个#include bits/stdc.h #define int long long //避免数据范围溢出 #define endl \n using namespace std; int n,k; // st[i][0]是第i块巧克力高度Hst[i][1]宽度W int st[100005][2];//多五个是为了空出来l和r初始的位置至少要比10^5多俩位置 // check函数给定正方形边长mid能否切出 k 块正方形巧克力 bool check(int mid){ int cnt0; for(int i0;in;i){ // 这块巧克力沿着高能切 H/mid 个宽能切 W/mid 个相乘就是总数 cnt(st[i][0]/mid)*(st[i][1]/mid); } return cntk; } void solve(){ cinnk; for(int i0;in;i){ cinst[i][0]st[i][1]; } // 二分边界最小边长l0最大可能边长r1e5题目H,W最大1e5 int l0,r100000;//!!!r我一开始写成n1了不对应该写最大的可能的边长 // 二分模板l1r 左闭右开找最大满足条件的值 while(l1r){ int midlr1;//等价 mid(lr)/2位运算更快 //左边是可行区间即l始终走在可行区间里面 if(check(mid)) lmid;// mid可行尝试更大的边长把左边界移到mid else rmid; } coutl; } signed main(){ //关流输入输出速度变快 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }曾经的题解但是我觉得写的不好应该看最新的#include bits/stdc.h #define int long long #define endl \n using namespace std; int n,k,st[100005][2]; //判断边长为mid(a)的正方形巧克力能不能把所有巧克力分成k份 //因为小朋友一共k人分成的巧克力边长必须是k的最大可能边长 bool check(int a){ int cnt0;//当前边长分成多少块巧克力了 for(int i0;in;i){ cnt(st[i][0]/a)*(st[i][1]/a); } return cntk; } void solve(){ int l0,r0;//二分的起始和结束 cinnk; for(int i0;in;i){ cinst[i][0]st[i][1]; rmax(max(r,st[i][0]),st[i][1]); } while(lr){ // 1等同于除以2只不过更快一些 int mid(lr1)1;//这里加一是因为下面rmid-1减一了 if(check(mid)){ lmid; } else{ rmid-1;//因为这里是mid-1所以上边是mid(lr1)1里面得加个1 } } coutl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }