```cpp // 请把代码粘贴在这里 ``` include using namespace std; int n,k; int maxn; int H[100010]; int W[100010]; int l,r,mid; int sum,ans; /猜想：二分难道是从11到以小明所拥有的最大巧克力的较小边为边长的正方形， 以1为左端点，以上述正方形的边长为右端点？取mid值，判断是否能切出等大的K块正方形巧克力， 如果可以，则将左指针向右移一位，再取mid,如果不可以，右指针向左移动一位，取mid, 要设置变量ans存储mid值，直到左指针>右指针,最后一次二分ans保留的值，即为最大边长/ / 问题：可最大边一定不行，除非是正方形，并且这n块巧克力必须全这么大，不剪枝吗，等等，难道是担心这两条边之间的边长可能符合要求？ 回答：在二分查找里，右边界表示的是：搜索范围的上限，而不是答案可能的最大值 / bool check(int x) { //注意：sum要清0 sum=0; for(int i=0;i =k) { return true; }else{ return false; } } int main() { cin>>n>>k; for(int i=0;i >H[i]>>W[i]; maxn=max(H[i],maxn); maxn=max(W[i],maxn); //不断更新最大边，存入maxn } l=1; r=maxn; while(l<=r) { mid=(l+r)/2; if(check(mid)) { ans=mid; l=mid+1; }else { r=mid-1; } } cout<<ans<<endl; return 0; }

```cpp // https://dashoj.com/d/lqbproblem/p/45 #include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; ll n, k, maxSide = 0; vector<pair<ll, ll>> vpll(N); bool check(ll len, ll k1) { int count = 0; // 记录能切几个 len * len 大的蛋糕 for (auto &c: vpll) count += (c.first / len) * (c.second / len); return count >= k; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) { cin >> vpll[i].first >> vpll[i].second; maxSide = max({maxSide, vpll[i].first, vpll[i].second}); } ll l = 0, r = maxSide; while (l <= r) { ll m = l + (r - l) / 2; if (check(m, k)) l = m + 1; else r = m - 1; } cout << r << endl; return 0; } ```

``` #include <bits/stdc++.h> using namespace std; const int N=1e5+10; int n,k; int a[N],b[N]; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } int l=0,r=1e5; while(l<r){ int mid=(l+r+1)/2; long long sum=0; for(int i=1;i<=n;i++){ sum+=(a[i]/mid)*(b[i]/mid); } if(sum>=k) l=mid; else r=mid-1; } cout<<l<<endl; } ```

import sys def check(mid): res = 0 for i in range(N): res += (H[i] // mid) (W[i] // mid) if res >= K: return True return False N,K = map(int,input().split()) H,W = [],[] for i in range(N): h,w = map(int,input().split()) H.append(h) W.append(w) l,r = 1, 10 5 while l > 1 if check(mid): l = mid else: r = mid - 1 print(l)

``` #include<bits/stdc++.h> using namespace std; int a[100005],b[100005]; int l,r = 1e9,mid; int n,k; int check(int x)//检测分得的巧克力总数量 { int c = 0; for(int i = 1; i <= n; i++) { c += (a[i]/x)*(b[i]/x); } return c >= k; } int main() { cin >> n >> k; for(int i = 1; i <= n; i ++) { cin >> a[i] >> b[i]; } while(r - l > 1) { mid = (l+r) >> 1; if(check(mid)) l = mid; // 如果切的数量大于人数, 则尽可能切大 else r = mid; // 如果切的数量少于人数，则切小 } cout << l; return 0; } ```

``` #include #define objl '\n' typedef long long ll; using namespace std; //数据结构在这里定义 const int N = 1e5 + 10; int n,k; int H[N]; int W[N];//第i块巧克力的数据 int maxn = 0;//最大的一块巧克力边长，它作为初始的r bool check(ll x){ int sum = 0; for(int i = 1; i<=n;i++){ //逐个切巧克力 sum = sum + (H[i]/x)*(W[i]/x); } if(sum >= k){ return true; }else{ return false; } } //要找边长的最大值也就是右边界 void bs(){ ll l = 1, r = maxn; ll ans = 1; while(l<=r){ //左闭右闭 ll mid = l + (r - l) / 2; //排除 [mid, right] if(check(mid)==false){ //说明边长太大，块数不够给小朋友 //mid以及mid以后的边长一定不满足条件 r = mid - 1; //mid是解区间内的一个值 }else if(check(mid)==true){//满足条件就记录一个答案，直到找不到为止 //可能Mid就是我要找的最大值 当l=mid+1后 //l-r之间再也找不到了 ans = mid; l = mid + 1; } } cout << ans << endl; } void solve(){ cin >> n >> k; for(int i =1;i <= n;i++){ cin >> H[i] >> W[i]; if(H[i] > maxn){ maxn = H[i];//作为r值 } if(W[i] > maxn){ maxn = W[i]; } } bs(); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;//多组数据要cin //cin >> t; t = 1; while(t--){ solve(); } return 0;//必须加return 0 } ```

``` #include<bits/stdc++.h> using namespace std; vector<pair<int,int>>cake; int n,k; bool check(int mid){ int sum = 0; for(auto x : cake){ int a = x.first / mid; int b = x.second / mid; sum += a * b; } if(sum >= k) return true; else return false; } int main(){ cin >> n >> k; for(int i = 1; i <= n; i++){ int x,y; cin >> x >> y; cake.push_back({x,y}); } 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; return 0; } ```

``` def check(d): global w,h cnt = 0 for i in range(n): cnt+=(w[i]//d)*(h[i]//d) if cnt>=k: return True else: return False n,k = map(int,input().split()) h =[0]*(n+10) w = [0]*(n+10) for i in range(n): h[i],w[i] = map(int,input().split()) l,r = 1,100000+10 while l<r: mid = (l+r)//2 if check(mid): l = mid+1 else: r = mid print(l-1) ```

``` #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<string> #include<vector> using namespace std; int n,k; struct node{ int height; int width; }; vector<node> qcl; bool check(int side){ int c=0; for(int i=0;i<n;i++){ c+=(qcl[i].height/side) *(qcl[i].width/side); } return c>=k; } int main(){ cin>>n>>k; int res=0; // 处理输入数据 for(int i=0;i<n;i++){ node ever; cin>>ever.height>>ever.width; qcl.push_back(ever); } int l=0,r=1e9; while(l<=r){ int mid=l+r>>1; if(check(mid)){ res=mid; l=mid+1; }else{ r=mid-1; } } cout<<res; return 0; } ```

``` #include< using namespace std; const int N=10e5+10; int h[N],w[N]; int n,k; bool check(int a){ int sum=0; for(int i=0;i<n;i++){ sum+=(h[i]/a)*(w[i]/a); if(sum>=k)return true; } return false; } int main(){ cin.tie(0)->sync_with_stdio(false); cin>>n>>k; for(int i=0;i<n;i++){ cin>>h[i]>>w[i]; } int l=1,r=10e5; /*注意边界*/ while(l<r){ int mid=l+(r-l+1>>1); if(check(mid))l=mid; else r=mid-1; } cout<<r; return 0; } ```