自动搬运

查看原文

来自洛谷，原作者为

	ZYX0716 **

搬运于2025-08-24 21:18:21，当前版本为作者最后更新于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;
}