考点

整数二分 获得额外条件求解

C++ 代码

# include <iostream>
using namespace std;
const int N = 1e5 + 10;

int h[N],w[N];

int n,k;

long long check(int x)  // 一个边长为x的正方形
{
    long long res = 0;
    for(int i = 0 ; i < n ; i++)
    {
        res += (long long)(h[i] / x) * (w[i] / x);
    }
    return res;
}

int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 0 ; i < n ; i++)
    {
        scanf("%d %d",&h[i],&w[i]);
    }
    int l = 1;
    int r = 1e5;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(check(mid) >= k)
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    printf("%d\n",r);
    return 0;
}