分析

• 本来想自己算一个最大边，记所有面积除以k个人，再开方，这个边界太接近反而可能小于最大边长，后来改成默认最大边就好，log收敛很快
• 二分，每次判断中间点是否可行
• 可行的标准就是每个mid*mid这么大，可分出的块数不小于k

C++ 代码

#include<bits/stdc++.h>
using namespace std;

//Tools

#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl   //nextline

//vars
const int N=1e5+10;

int n,k;
int H[N],W[N];

int A;//可能的最大边长

//fun
void init();
bool check(int );
int bs(int ,int );

int main(){
    init();
    cout<<bs(1,A)<<endl;
    return 0;

}

void init(){
    cin>>n>>k;
    // unsigned long long sum=0;//1e19
    ffor(i,0,n){
        scanf("%d %d",&H[i],&W[i]);
        // sum+=(H[i] * W[i]);
    }
    // sum/=k;
    // A=sqrt(sum)+1;这里有问题，对超大数开方会出错
    A=N;
    // out(A);nl;
}

bool check(int a){
    int t=k;
    ffor(i,0,n){
        t-=(H[i]/a) * (W[i]/a);
        if(t<=0) return true;
    }
    return false;
}
int bs(int l,int r){
    if(l>r) return -1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}