经典二分求解分巧克力

看题目就知道这是一道很经典的二分算法的题，给定 N 块长方形巧克力，要切出 K 个大小相同的整数边长正方形，求正方形最大边长。
知道这个我们就可以猜测边长了，每块Hi×WiH_i \times W_iHi​×Wi​的巧克力，能切出的正方形数量为⌊Hi/mid⌋×⌊Wi/mid⌋\lfloor H_i/mid \rfloor \times \lfloor W_i/mid \rfloor⌊Hi​/mid⌋×⌊Wi​/mid⌋。把所有巧克力的数量加起来，如果总和≥K\ge K≥K，说明这个边长可行，然后就可以直接剪枝了，直接尝试更大的边长；如果边长大了再尝试更小的。
二分范围根据题目设左边界 1，右边界最大可取10510^5105
数据规模：N≤105N \le 10^5N≤105，二分最多 30 轮，总复杂度O(Nlog⁡(105))O(N\log(10^5))O(Nlog(105))，可以通过

解题代码

#include<iostream>#include<vector>usingnamespacestd;typedeflonglongll;constintMAXN=1e5+10;inth[MAXN],w[MAXN];intN,K;// 判断边长为x的时候，是否能切出至少K块boolcheck(intx){ll total=0;for(inti=0;i<N;i++){total+=(ll)(h[i]/x)*(w[i]/x);if(total>=K)returntrue;// 提前剪枝，防止溢出}returntotal>=K;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>K;for(inti=0;i<N;i++){cin>>h[i]>>w[i];}intl=1,r=100000;intans=0;while(l<=r){intmid=l+(r-l)/2;if(check(mid)){ans=mid;l=mid+1;// 可行，尝试更大}else{r=mid-1;// 不可行，缩小}}cout<<ans<<endl;return0;}

这个题目就是道纯二分的模板题，其实很像猜数字，这样子就好理解了。