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

题目大意

有许多彩纸，给出这些彩纸的长和宽，要求用这些彩纸减最少

k

个正方形，求满足条件的最大正方形边长。

思路

从大到小枚举正方形边长，每次枚举计算该边长最多能剪出多少个正方形，即枚举每张彩纸，累加每张彩纸能剪出的正方形数

\lfloor W_j\div i \rfloor \times \lfloor H_j\div i \rfloor

，即长能摆的正方形数乘宽能摆的正方形数，而如果直接用彩纸面积除以正方形面积是错误的，因为剪下正方形后可能会有剩余且不能摆出正方形的部分。若能剪出的正方形总数

s\ge k

，就输出这个边长。
具体细节看代码吧！

代码

CPP

#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;
}

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

文章操作

题目大意

思路

代码

相关推荐

评论

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