第十六届蓝桥杯病愈训练--8

标题链接：1227. 分巧克力 - AcWing题库

思绪：二分答案，每次二分边长
代码：

1. #include<bits/stdc++.h>
2. using namespace std;
4. typedef pair<int,int> PII;
6. #define N 100010
8. int n,k;
9. PII a[N];
11. bool check(int mid){
12.     int cnt=0;
13.     for(int i=1;i<=n;i++){
14.         if(a[i].first<mid||a[i].second<mid)continue;
15.         cnt+=(a[i].first/mid)*(a[i].second/mid);
16.     }
17.     if(cnt>=k)return true;
18.     return false;
19. }
21. int main(){
22.    
23.     cin>>n>>k;
24.     for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
25.    
26.     int l=1,r=N;
27.     while(l<=r){
28.         int mid=l+r>>1;
29.         if(check(mid))l=mid+1;
30.         else r=mid-1;
31.     }
32.    
33.     cout<<r<<endl;
34.    
35.    
36.     return 0;
37. }

复制代码