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

· · 题解

题目大意

有许多彩纸，给出这些彩纸的长和宽，要求用这些彩纸减最少 k 个正方形，求满足条件的最大正方形边长。

思路

从大到小枚举正方形边长，每次枚举计算该边长最多能剪出多少个正方形，即枚举每张彩纸，累加每张彩纸能剪出的正方形数 \lfloor W_j\div i \rfloor \times \lfloor H_j\div i \rfloor，即长能摆的正方形数乘宽能摆的正方形数，而如果直接用彩纸面积除以正方形面积是错误的，因为剪下正方形后可能会有剩余且不能摆出正方形的部分。若能剪出的正方形总数 s\ge k，就输出这个边长。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,s,x[505],y[505];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
        s+=x[i]*y[i];
    }
    cin>>k;
    s/=k;
    s=sqrt(s);
    //s为正方形边长上限
    //因为按照面积除肯定比按照边长除多（前面有讲），所以比是s大的正方形边长一定不可能满足要求
    //所以从s开始枚举
    for(int i=s;i>=1;--i){
        int ans=0;
        for(int j=1;j<=n;++j)ans+=(x[j]/i)*(y[j]/i);
        //累加个数
        if(ans>=k){
            cout<<i<<"\n";
            //满足要求就输出
            return 0;
        }
    }
    return 0;
}