A41769. 最大值
填空题
困难
知识点
题目描述
最大值
题目描述
手工课上老师拿出N张长方形彩纸，且每张彩纸上都画着W*H的网格（网格铺满整张彩纸）。现在老师将N张彩纸裁剪出K张大小相同的正方形，并且要使裁剪出的正方形的边长最大（裁剪的正方形边长必须为整数）。
例如：N=2，有2张彩纸，第一张彩纸W=4，H=3；第二张彩纸W=5，H=4；K=6，裁剪的6个正方形边长最大是2。
当给出N张长方形彩纸W和H，及K的值，请计算出将N张彩纸裁剪出K张大小相同的正方形，正方形的边长最大是多少（裁剪的正方形边长必须为整数）。
输入描述
第一行输入两个正整数N，K（1<N<100，1<K<100），N表示彩纸数量，K表示需裁剪的正方形数量，两个正整数之间一个空格隔开
第二行开始，输入N行，每行输入两个正整数Wi，Hi（1<Wi<1000，1<Hi<1000，且Wi!=Hi），Wi表示彩纸的长度，Hi表示彩纸的宽度，两个正整数之间一个空格隔开
输出描述
输出一个正整数，表示将N张彩纸裁剪出K张大小相同的正方形的边长最大是多少（裁剪的正方形边长必须为整数），如果不能裁剪出K张正方形就输出“-1"。
样例输入
2 6
4 3
5 4
样例输出
2
参考答案
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,k;
struct nod{
int w,h;
}a[105];
bool check(int x){
int ans=0;
for(int i=1;i<=n;i++)
ans+=(a[i].h/x)*(a[i].w/x);
return ans>=k;
}
int main()
{
cin>>n>>k;
int sum=0,maxn=0;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].h;
sum+=a[i].w*a[i].h;
maxn=max(maxn,min(a[i].w,a[i].h));
}
if(sum<k){
cout<<-1<<endl;
return 0;
}
int L=1,R=maxn,mid;
while(L<R-1){
mid=(L+R)/2;
if(check(mid)) L=mid;
else R=mid;
}
if(check(R)) cout<<R<<endl;
else cout<<L<<endl;
return 0;
}
上一题
下一题