题目描述

blablabla

思路

在理解题意后发现并不容易找出最合适的边长，所以想到使用二分，相当于多加了一个条件，以此来一步步逼近最合适的边长

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100010;
int n,k;
int h[N],w[N];

bool check(int mid){
    LL num = 0;
    for(int i = 0;i < n;i++){
        // 这里使用LL是因为如果边长取1，就会是10的5次方的平方，这个可能爆
        num += (LL)(h[i] / mid) * (w[i] / mid);
        if(num >= k) return true;
    }

    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i++){
        scanf("%d%d",&h[i],&w[i]);
    }

    // 二分模板二，根据check来判断
    int l = 1,r = 1e5;
    while(l < r){
        int mid = (l + r + 1)>> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d",l);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla