acwing 每日一题 1227 分巧克力（整数二分)_24块儿,正方形。巧克力用当切了几块儿,完好无?损-程序员宅基地

儿童节那天有 K

位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N
块巧克力，其中第 i 块是 Hi×Wi

的方格组成的长方形。

为了公平起见，小明需要从这 N
块巧克力中切出 K

块巧克力分给小朋友们。

切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块 6×5
的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3

的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式

第一行包含两个整数 N
和 K

。

以下 N
行每行包含两个整数 Hi 和 Wi

。

原题如下

输入保证每位小朋友至少能获得一块 1×1

的巧克力。
输出格式

输出切出的正方形巧克力最大可能的边长。
数据范围

1≤N,K≤105
,
1≤Hi,Wi≤105

输入样例：

2 10
6 5
5 6

输出样例：

难度：简单
时/空限制： 1s / 64MB
总通过数： 2631
总尝试数： 5170
来源：第八届蓝桥杯省赛C++A/B组,第八届蓝桥杯省赛JAVAA/B组
算法标签
二分

题目分析

思路同浮点二分，不过代码实现有一点不同。

通过代码

解法一

#include<stdio.h>
#include<iostream>
using namespace std;

int a[(int)1e5+10][2];
int n,k;
	
int l=1,r=1e5;	
bool check(int mid){
    
	long long sum=0;
	for(int i=1;i<=n;++i){
    
		sum+=(a[i][1]/mid)*(a[i][0]/mid);
		if(sum>=k) return true;
	}
	
	return false;
}
int main(){
    
	
	cin>>n>>k;
	for(int i=1;i<=n;++i){
    
		cin>>a[i][0];
		cin>>a[i][1];
	}
	while(l<r){
    
		int mid=(l+r)/2+1//向上取整，则mid包括在左区间;
		if(check(mid)){
    
			l=mid;
		}
		else r=mid-1//为了避免死循环，r减一;
		
	}
	cout<<r<<endl;
	return 0;
}

解法二

#include<stdio.h>
#include<iostream>
using namespace std;

int a[(int)1e5+10][2];
int n,k;
	
int l=1,r=1e5;	
bool check(int mid){
    
	long long sum=0;
	for(int i=1;i<=n;++i){
    
		sum+=(a[i][1]/mid)*(a[i][0]/mid);
		if(sum>=k) return true;
	}
	
	return false;
}
int main(){
    
	
	cin>>n>>k;
	for(int i=1;i<=n;++i){
    
		cin>>a[i][0];
		cin>>a[i][1];
	}
	while(l<r){
    
		int mid=(l+r)/2//向下取整，则mid包括在右区间;
		if(check(mid)){
    
			l=mid+1;//为了避免死循环，l加一;
		}
		else r=mid
		
	}
	cout<<r-1<<endl;//此解法会导致解多1，减去 推荐解法一。 
	return 0;
}

yxc大佬的模板

在这里插入图片描述
大佬在模板一中结果忘了减一qwq

本文链接：https://blog.csdn.net/chimp10/article/details/112725354

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

HDFS：Edits和Fsimage详解与合并流程_为什么要将edit logs和fsimage定期合并。-程序员宅基地

文章浏览阅读2.6k次，点赞8次，收藏19次。HDFS：Edits和Fsimage详解与合并流程NameNode如何管理和存储元数据计算机中存储数据有两种：内存或磁盘元数据存储磁盘: 存储磁盘无法面对客户端对元数据信息的任意的快速低延迟的响应，但是安全性高元数据存储内存：元数据存放内存，可以高效的查询以及快速响应客户端的查询请求，数据保存在内存，如果断电，内存中的数据全部丢失因此，考虑上述两种存储方式的优缺点，HDFS采用了内存+磁盘的形式来管理元数据。即: NameNode(内存)+FsImage文件. 其中，NameNode文件维护了文件_为什么要将edit logs和fsimage定期合并。

import math在python种中的意思,Python中import使用-程序员宅基地

文章浏览阅读2.4w次，点赞2次，收藏10次。import的使用举例：#coding:utf-8import mathr=5print("半径是5的圆面积是:%.2f"%(math.pi*r**2))import math的意思为从Python标准库中引入math.py模块，这是Python中定义的引入模块的方法。import的标准语法如下：import module1[, module2[,… moduleN]]表示允许一个import导入..._import math

OpenAI新版GPT-4 Turbo向付费ChatGPT用户开放使用-程序员宅基地

文章浏览阅读447次，点赞8次，收藏8次。GPT-4 Turbo 还引入了若干新功能，如支持 JSON 模式、可复现输出和并行函数调用等，这些都是为了提高模型的实用性和灵活性。OpenAI近日宣布其新版GPT-4 Turbo模型正式向付费ChatGPT用户开放，该模型在多个关键方面进行了升级和优化。这一改进比原有的 GPT-4 模型的上下文窗口大得多，使得模型在处理长篇文章或复杂对话时更加高效。该模型在多个关键方面进行了升级和优化，旨在提供更强大的性能和更低的使用成本。这使得 Turbo 模型在理解和生成更复杂、更细致的内容方面具有更强的能力。

编译运行openvslam_libfbow.so.0.0-程序员宅基地

文章浏览阅读2k次。在编译openvslam的过程中遇到了如下几个问题：1、有关opencv中undistortPoints函数参数的问题：opencv版本过低，选用高版本即可。2、pangolin中函数was not declared。参考https://blog.csdn.net/liudahanghang/article/details/80601136把pangolin版本回退到文档中指定的ad8b5f8即可。3、报错如下：/home/yasaburo3/project/openvslam/test/open_libfbow.so.0.0

禅道安装详解_禅道安装教程-程序员宅基地

文章浏览阅读539次。1、http://www.zentao.net/download/79888.htmlhttp://www.cnblogs.com/qiongmiaoer/p/3533728.html http://www.zentao.net/_禅道安装教程

C语言程序设计部分基础代码（已用MD编辑器重写一篇博客）_c语言编程基础代码-程序员宅基地

文章浏览阅读9.4k次，点赞7次，收藏36次。C语言程序设计部分基础代码（纯手敲，待完善）_c语言编程基础代码