P8647 [蓝桥杯 2017 省 AB] 分巧克力

P8647 [蓝桥杯 2017 省 AB] 分巧克力

[P8647 [蓝桥杯 2017 省 AB] 分巧克力](https://www.luogu.com.cn/problem/P8647?contestId=150480
P8647 [蓝桥杯 2017 省 AB] 分巧克力)

题意

给n个边长为不等的巧克力,要分给三个小盆友,这些巧克力必须是正方形且大小必须相同,求最后要分得几块。

思路

  1. 根据样例怎么输入输出
  2. 二分模版套用,然后对每块巧克力进行遍历,计算每块巧克力能分成的块数,并累加到ans中。
  3. 比较大小,如果ans大于等于k,左边界l更新为mid+1,同时将ans更新为mid,如果ans小于k,说明当前mid值不满足要求,将右边界r更新为mid-1。

坑点

  1. 最难的在于怎么计算巧克力的面积,然后二分查找。 二分模版学会套用。

算法一:基础的二分答案

时间复杂度
  • 输出大小: 1.83265209197998 MiB
  • 编译时间: 0.59s
实现步骤
  1. 首先,输入两个整数n和k,分别代表巧克力的数量和需要分的块数。
  2. 二分查找对每块巧克力进行遍历,计算每块巧克力能分成的块数,并累加到ans中
  3. 然后进行判断是否输出。
代码
 #include<iostream>
using namespace std;
int main()
{
    int n,k;//首先,输入两个整数n和k,分别代表巧克力的数量和需要分的块数。
    int h[100000];
    int w[100000];//两个巧克力的边长 
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>h[i]>>w[i];
    //二分查找
    int r = 100001;//初始化一个右边界r为100001
    int l = 1;//一个左边界l为1
    int x = 0;//设定一个答案ans为0。
    while(l<=r)//然后进入while循环,当左边界小于等于右边界时,进行二分查找。
    {
        int mid = (l+r)/2;//在每次循环中,会计算中间值mid为(l+r)/2,
        int ans = 0;//初始化一个计数器ans为0,用来记录巧克力最大能分成几块。
        for(int i=0;i<n;i++)
            ans += (h[i]/mid)*(w[i]/mid);
            //然后对每块巧克力进行遍历,计算每块巧克力能分成的块数,并累加到ans中。
        if(ans>=k)接着,程序会比较ans和k的大小,如果ans大于等于k.
        {
            l = mid+1;//左边界l更新为mid+1,
            x = mid;//同时将ans更新为mid
        }
        else r = mid-1;//如果ans小于k,说明当前mid值不满足要求,将右边界r更新为mid-1。
    }
    cout<<x<<endl;//最后,输出答案ans即为能够满足分成k块巧克力的最大边长。
    return 0;
}

总结

二分答案是二分查找里特殊的一种。