题目链接
一些话
跟cf上的一道铺设地板的题的手法有共通之处，
都是拿长宽/地板边长，然后相乘
切入点
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
边长与数量成负相关，符合二分的特征
流程
二分答案check函数伪代码（流程)
// mid长度，cnt计数，枚举巧克力，用长宽除mid再相乘得到数字加入cnt，最后再和k比较
二分边界变化
// 因为mid与cnt成反比，所以cnt>k了就缩小左边界让mid变大，cnt<k了就缩小右边界让mid变小，
// 巧克力最大就是边长最大，边长最大就是mid最大，为了让mid最大，当cnt等于k时缩小左边界就可以让mid最大
套路
ac代码
//16 : 52 ~17:07wa // mid长度，cnt计数，枚举巧克力，用长宽除mid再相乘得到数字加入cnt，， // 因为mid与cnt成反比，所以cnt>k了就缩小左边界让mid变大，cnt<k了就缩小右边界让mid变小， // 巧克力最大就是边长最大，边长最大就是mid最大，为了让mid最大，当cnt等于k时缩小左边界就可以让mid最大 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 10; int n,k; int l[N],w[N]; bool check(int mid){ int cnt = 0; for(int i = 0;i < n;i++){ cnt += (l[i] / mid) * (w[i] / mid); } if(cnt >= k) return true; else return false; } int main(){ cin >> n >> k; for(int i = 0;i < n;i++){ scanf("%d%d",&l[i],&w[i]); } int l = 1,r = 1e5; while(l < r){ int mid = l + r + 1>> 1; if(check(mid)) l =mid ; else r = mid - 1; } cout << l << endl; return 0; }
