分巧克力 刷题笔记

/*
分巧克力 解题思路 
二分 
直接检查看答案是否符合题目条件
对于一块边长分别为x 和y的巧克力\\
假设我们输入检查的数为k 
其能分割成的 k*k 的巧克力的块数为
(x/k)*(y/k)
因为c++里面的除法是下取整的所以我们不用考虑奇偶数 是否能整除

将每一块巧克力能分成的k*k的巧克力块数加上计数器
一旦计数器超过了孩子数 我们就返回true;
如果check 不通过的话 可能是分的太大了
所以答案小于mid
 于是我们让r=mid-1
 如果check通过
 则答案>=mid 所以我们让l=mid   
重点 讨论边界情况
例如案例中 
2 10
6 5
5 6

输出2 
当 l指向2 r指向3 
mid=(l+r)>>1;的话 mid 是2 
此时check可以通过 
但是l=2,r=3;
如果还是l=mid=2则陷入死循环
于是 我们让mid=(l+r+1)>>1
让其进行上取整
则 mid=3;
check不通过 
此时 r=mid-1=l；
退出循环
 
输出l或者r即可 
 
*/ 

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
struct node{
    int x;
    int y;    
}a[N];
int n,k;
bool check(int p){
    int cnt=0;
    bool flag=false;
//    cout<<"p is "<<p<<endl;
    for(int i=0;i<n;i++){
        cnt=cnt+(a[i].x /p)*(a[i].y /p);
        //cout <<cnt<<endl; 
        if(cnt>=k){
            flag= true;
            break;
        }
        
    }
    return flag;
}
int main(){
    cin>>n>>k;
    int r=0;
    for(int i=0;i<n;i++){
        cin>>a[i].x >>a[i].y;
        if(a[i].x >a[i].y ){
            if(a[i].x >r){
                r=a[i].x ;
            }
        }else{
            if(a[i].y >r){
                r=a[i].y ;
            }
        }        
    }
//    cout<<r<<endl;
    int l=0;
    while(l<r){
        int mid=(l+r+1)>>1;
        //cout<<mid<<endl;
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
        //cout<<"l is"<<l<<endl<<"r is "<<r<<endl;  
    }
    cout <<l;
    return 0; 
}