AcWing 1227. 分巧克力 题解 二分

题目

思路

• 题目意思：要把$N$块巧克力切成边长完全一样的正方形小块，至少$K$块，求切成的巧克力块的最大边长
• 对于一块巧克力而言，长为$H$，宽为$W$，若想切成边长为$X$的正方形小块，可以切$\lfloor$$\frac{H}{X}$$\rfloor \times \lfloor$$\frac{W}{X}$$\rfloor$块
• 我们发现，可以切成的块数与最终切成个一个个正方形的边长是成反比的
  
  由此我们也发现，随着边长的增大，可以切成的块数呈单调递减的趋势，从而想到可以用二分法来二分出符合条件的最大的边长
• 判断函数的编写

bool count(int m)
{ 
   
    int res=0;
    for(int i=1;i<=n;i++)
    { 
   
        res+=(h[i]/m)*(w[i]/m);
        if(res>=k) return true;
    }
    return false;
}

用当前需要判断的边长去判断，每块巧克力这么切，最后能不能切到总共$k$块

• 二分模板

    int l=1,r=1e5;
    while(l<r)
    { 
   
        int mid=(l+r+1)>>1;
        if(count(mid)) l=mid;
        else r=mid-1;
    }

• 二分上下界
  输入保证每位小朋友至少能获得一块 1×1 的巧克力，所以二分下界为1
  大巧克力块的长宽最大值都可以取到$10^5$，所以上界是$10^5$
• 二分递归判断
  对着那个反比例函数的图来看更为直观一点
  如果mid处符合条件，那么比mid小的地方也符合条件，mid处也符合条件，那么$l=mid$，在mid以及mid的后面继续递归的找（我们要找的是反比例函数里面的边长正好使块数为k的那个临界点）
  如果mid处不符合条件，那么比mid大的地方也不符合条件，所以要在mid的前面去找，因为mid处不符合，所以上界要在mid的前一位，即$r=mid-1$
  最后再相应的去调整mid的求法

代码

#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N],w[N];
int n,k;
bool count(int m)
{ 
   
    int res=0;
    for(int i=1;i<=n;i++)
    { 
   
        res+=(h[i]/m)*(w[i]/m);
        if(res>=k) return true;
    }
    return false;
}
int main()
{ 
   
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d%d",&h[i],&w[i]);
    
    int l=1,r=1e5;
    while(l<r)
    { 
   
        int mid=(l+r+1)>>1;
        if(count(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",l);
    return 0;
}

今天的文章AcWing 1227. 分巧克力 题解 二分分享到此就结束了，感谢您的阅读。