经典二分求解分巧克力

看题目就知道这是一道很经典的二分算法的题给定 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))可以通过解题代码#includeiostream#includevectorusingnamespacestd;typedeflonglongll;constintMAXN1e510;inth[MAXN],w[MAXN];intN,K;// 判断边长为x的时候是否能切出至少K块boolcheck(intx){ll total0;for(inti0;iN;i){total(ll)(h[i]/x)*(w[i]/x);if(totalK)returntrue;// 提前剪枝防止溢出}returntotalK;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinNK;for(inti0;iN;i){cinh[i]w[i];}intl1,r100000;intans0;while(lr){intmidl(r-l)/2;if(check(mid)){ansmid;lmid1;// 可行尝试更大}else{rmid-1;// 不可行缩小}}coutansendl;return0;}这个题目就是道纯二分的模板题其实很像猜数字这样子就好理解了。