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

题意

读完题后可得知：有

n

张大小为

w \times h

的纸，将这些纸剪成边长为

len

的正方形纸，至少

k

张，且纸可以不用完，但裁剪出的正方形边长必须为整数。请你求出满足条件的最大

len

的值。

分析

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

\ge k

。

注意：求第

i

张纸可以剪出多少个正方形时，要分别求出行和列除以

len

的商，再相乘。

Code

CPP

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

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

文章操作

题意

分析

Code

相关推荐

评论

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