分巧克力（刷题赛）

reference

站在用户的角度思考问题，与客户深入沟通，找到屏山网站设计与屏山网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都网站设计、成都网站制作、企业官网、英文网站、手机端网站、网站推广、空间域名、雅安服务器托管、企业邮箱。业务覆盖屏山地区。

#include
#include
using namespace std;
/*使得将巧克力按照边长maxX进行切分
，切分成的份数要大于等于K，
而如果按照maxX+1进行切割
，将不再能够切出K块。
如果从1-逐个查找，那么肯定超时，所以采用二分查找。
*/
int n,k,a[],b[];//a 4 high ,b 4 wide
bool ok(int x){
    int cnt=0;
    for (int i = 1; i <= n; i ++ ){
        cnt+=(a[i]/x)*(b[i]/x);//可以切割成的边长合理的正方形巧克力的块数
        if(cnt>=k){
            return true;
        }
    }
    return false;
}
int main()
{
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
	    cin >> a[i]>>b[i];
	}
	int l = 0,r = ;
	while(l<=r){
	    int m = l/2+r/2;
	    if(ok(m)){
	        l=m+1;
	    }else{
	        r=m-1;
	    }
	}
	cout<


题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力，其中第 ii 块是 H_i \times WiH

i



×Wi 的方格组成的长方形。为了公平起见，
小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
形状是正方形，边长是整数;
大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入描述

第一行包含两个整数 N,KN,K (1 \leq N, K \leq 10^51≤N,K≤10

5

)。
以下 N 行每行包含两个整数 H_i,W_iH

i



,W

i



(1 \leq H_i, W_i \leq 10^51≤H

i



,W

i



≤10

5

)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出描述

输出切出的正方形巧克力最大可能的边长。
输入输出样例

示例

输入
2 10

6 5

5 6

copy

输出
2

copy

运行限制

最大运行时间：1s

最大运行内存: 256M

本文由博客一文多发平台 OpenWrite 发布！
            
            
                            

                分享名称：分巧克力（刷题赛）                

                URL链接：http://wjwzjz.com/article/dsogoie.html

新网创想网站建设，新征程启航

分巧克力（刷题赛）

其他资讯