网站开发相关专业,无锡模板网站,广东网站建设方便,登录百度app题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力#xff0c;其中第 ii 块是 HiWiHiWi 的方格组成的长方形。为了公平起见#xff0c;
小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克…题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。为了公平起见
小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足 形状是正方形边长是整数; 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么
输入描述
第一行包含两个整数 N,KN,K (1≤N,K≤1051≤N,K≤105)。
以下 N 行每行包含两个整数 Hi,WiHi,Wi (1≤Hi,Wi≤1051≤Hi,Wi≤105)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
输入输出样例
示例 输入 2 10
6 5
5 6输出 2运行限制
最大运行时间2s最大运行内存: 256M
总通过次数: 10390 | 总提交次数: 11980 | 通过率: 86.7%
难度: 困难 标签: 2017, 省赛, 二分
思路
定义bool型的判断函数判断把每块巧克力切后的块数相加是否符合小朋友的要求即大于等于K
然后用二分法寻找即可
代码 #include iostream
#include algorithm
#include vector
#include math.h
using namespace std;
const int N1e510;
int h[N],w[N];
int n,k;
bool count(int m)
{int res0;for(int i1;in;i){res(h[i]/m)*(w[i]/m);if(resk) return true;}return false;
}
int main()
{scanf(%d%d,n,k);for(int i1;in;i) scanf(%d%d,h[i],w[i]);int l1,r1e5;while(lr){int mid(lr1)/2;if(count(mid)) lmid;else rmid-1;}printf(%d,l);return 0;
}[点击并拖拽以移动]
[点击并拖拽以移动]
