题目：
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块巧克力高度H，st[i][1]宽度W int st[100005][2];//多五个是为了空出来l和r初始的位置，至少要比10^5多俩位置 // check函数：给定正方形边长mid，能否切出 >=k 块正方形巧克力 bool check(int mid){ int cnt=0; for(int i=0;i<n;i++){ // 这块巧克力，沿着高能切 H/mid 个，宽能切 W/mid 个，相乘就是总数 cnt+=(st[i][0]/mid)*(st[i][1]/mid); } return cnt>=k; } void solve(){ cin>>n>>k; for(int i=0;i<n;i++){ cin>>st[i][0]>>st[i][1]; } // 二分边界：最小边长l=0，最大可能边长r=1e5（题目H,W最大1e5） int l=0,r=100000;//!!!r我一开始写成n+1了，不对，应该写最大的可能的边长 // 二分模板：l+1<r ，左闭右开找最大满足条件的值 while(l+1<r){ int mid=l+r>>1;//等价 mid=(l+r)/2，位运算更快 //左边是可行区间，即l始终走在可行区间里面 if(check(mid)) l=mid;// mid可行，尝试更大的边长，把左边界移到mid else r=mid; } cout<<l; } 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 cnt=0;//当前边长分成多少块巧克力了 for(int i=0;i<n;i++){ cnt+=(st[i][0]/a)*(st[i][1]/a); } return cnt>=k; } void solve(){ int l=0,r=0;//二分的起始和结束 cin>>n>>k; for(int i=0;i<n;i++){ cin>>st[i][0]>>st[i][1]; r=max(max(r,st[i][0]),st[i][1]); } while(l<r){ // >>1等同于除以2，只不过更快一些 int mid=(l+r+1)>>1;//这里加一是因为下面r=mid-1减一了 if(check(mid)){ l=mid; } else{ r=mid-1;//因为这里是mid-1，所以上边是mid=(l+r+1)>>1，里面得加个1 } } cout<<l; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
