分巧克力（蓝桥杯C/C++B组真题详解）

目录

题目：​编辑

 题目思路：

代码详解：

题目：

 题目思路：

因为答案唯一

且分布在一个区间里面

我们可以想到二分答案

直到找到最小的满足的条件的

合适答案

代码详解：

#include<iostream>
using namespace std;
const int N=1e5+6;
int a[N],b[N];

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);

    int l=1,r=N;
    while(l<r){
        int mid=l+r>>1;
        int sum=0;
        for(int i=1;i<=n;i++){
            int x=a[i]/mid;
            int y=b[i]/mid;
            sum+=x*y;
        }

        if(sum<k) r=mid;
        else l=mid+1;

    }

    cout<<l-1;//l对于取到正确答案仍然会加1，所以最后要减1
    return 0;
}

PS:这题其实理解了二分，时间复杂度不难，通过对时间的计算，就可以知道采用二分时间复杂度在O(Nlog2N)，条件下的时间在1秒之内，所以可以得出答案。

PPS:建议做事情从最重要的事情一件一件的去做，不重要的先不管，行动起来，你就会成功。

6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666