题解：B4285 [蓝桥杯青少年组省赛 2022] 最大值

_Z_YX_ · 2025-04-14 22:07:19 · 题解

题意

读完题后可得知：有 n 张大小为 w \times h 的纸，将这些纸剪成边长为 len 的正方形纸，至少 k 张，且纸可以不用完，但裁剪出的正方形边长必须为整数。请你求出满足条件的最大 len 的值。

分析

典型的二分答案。模拟正方形的边长，每张彩纸单独累加其可剪成的正方形数量，最后判断剪出的正方形个数是否 \ge k。

注意：求第 i 张纸可以剪出多少个正方形时，要分别求出行和列除以 len 的商，再相乘。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,w[505],h[505],k,l,r;
bool check(int mid){//判断边长为mid时是否可以剪出k个正方形。
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=(w[i]/mid)*(h[i]/mid);
        if(sum>=k)return 1;
    }
    return 0;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&w[i],&h[i]);
        r=max(r,max(w[i],h[i]));//正方形边长的最大值
    }
    scanf("%lld",&k);
    while(l<=r){//二分答案
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    printf("%lld",r);//输出正方形的最大边长
    return 0;
}