二分法，ac不了，蓝桥分巧克力

Question

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, k;
struct node
{
    int w;
    int h;
}c[N];
bool check(int x)
{
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        num += (c[i].h * c[i].w) / (x * x);
    }
    if (num >= k)
        return true;
    else
        return false;
}
int main()
{
    cin >> n >> k;
    int left = 1;
    int right = 100000;
    for (int i = 0; i < n; i++)
    {
        cin >> c[i].h >> c[i].w;
        if (c[i].h > right)
            right = c[i].h;
        if (c[i].w > right)
            right = c[i].w;
    }
    int ans = 0;
    while (left<=right)
    {
        int mid = (right + left) / 2;
        if (check(mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}

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

题目描述

儿童节那天有 $K$ 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times W_i$ 的方格组成的长方形。

为了公平起见，小明需要从这 $N$ 块巧克力中切出 $K$ 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数。

2. 大小相同。

例如一块 $6 \times 5$ 的巧克力可以切出 $6$ 块 $2 \times 2$ 的巧克力或者 $2$ 块 $3 \times 3$ 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小 $H_i$ 计算出最大的边长是多少么？

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1 \le N,K \le 10^5)$。

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1 \le H_i,W_i \le 10^5)$。

输入保证每位小朋友至少能获得一块 $1 \times 1$ 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

样例 #1

样例输入 #1

2 10  
6 5  
5 6

样例输出 #1

2

样例可以过，但是oj上过不了，哪里错了

Answer 1

引自免费微信小程序：皆我百晓生

问题出在二分查找的边界设置上，题目要求切出的巧克力边长是整数，但是你的二分查找的边界用的是1和100000，也就是说在这个范围内进行查找。而实际上，切出的巧克力边长应该在$1$到所有巧克力中最大的宽度和高度之间的最小值中进行查找。

具体来说：

1. 首先，需要在输入巧克力的时候记录下最大的宽度和高度，作为最大边界。

2. 在二分查找的时候，将边界的左边界设置为1，右边界设置为最大的宽度和高度中的较小值。

修改后的代码如下所示：

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, k;
struct node
{
    int w;
    int h;
}c[N];
bool check(int x)
{
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        num += (c[i].h * c[i].w) / (x * x);
    }
    if (num >= k)
        return true;
    else
        return false;
}
int main()
{
    cin >> n >> k;
    int left = 1;

    // 添加记录最大宽度和高度
    int max_size = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> c[i].h >> c[i].w;
        if (c[i].h > max_size)
            max_size = c[i].h;
        if (c[i].w > max_size)
            max_size = c[i].w;
    }

    // 将边界的右边界设置为最大宽度和高度中的较小值
    int right = max_size;

    int ans = 0;
    while (left <= right)
    {
        int mid = (right + left) / 2;
        if (check(mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}

这样修改后的代码，应该能够在OJ上通过了。