每日算法打卡:分巧克力 day 9
文章目录
- 原题链接
- 题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例:
- 输出样例:
- 题目分析
- 示例代码
原题链接
1227. 分巧克力
题目难度:简单
题目来源:第八届蓝桥杯省赛C++ A/B组,第八届蓝桥杯省赛Java A/B/C组
题目描述
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力,其中第 i 块是 H i × W i H_i \times W_i Hi×Wi 的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足:
- 形状是正方形,边长是整数
- 大小相同
例如一块 6 × 5 6 \times 5 6×5 的巧克力可以切出 6 块 2 × 2 2 \times 2 2×2 的巧克力或者 2 块 3 × 3 3 \times 3 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?
输入格式
第一行包含两个整数 N 和 K。
以下 NN 行每行包含两个整数 H i H_i Hi 和 W i W_i Wi。
输入保证每位小朋友至少能获得一块 1 × 1 1 \times 1 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1 ≤ N , K ≤ 1 0 5 1 \le N,K \le 10^5 1≤N,K≤105,
1 ≤ H i , W i ≤ 1 0 5 1 \le H_i,W_i \le 10^5 1≤Hi,Wi≤105
输入样例:
2 10
6 5
5 6
输出样例:
2
题目分析
这道题就是将n个矩形,切出尽可能大的等长的k个正方形,求最大的可能正方形边长
我们可以发现一个规律,边长越大,切出来的正方形个数就越少,那我们其实是可以用公式表示出来每一个矩形能切多少块正方形的
假设正方形边长为x,最终切出来的正方形个数就是
⌊ W i x ⌋ × ⌊ H i x ⌋ \lfloor \frac{W_i}{x} \rfloor \times \lfloor \frac{H_i}{x} \rfloor ⌊xWi⌋×⌊xHi⌋
这样,我们就可以看出来,块数是和边长一定是一个递减的函数关系
我们需要找到一个个数大于等于k的对应的x的最大值
实际上就只需要找到对应的这个点,我们就可以使用二分的做法
那么判断的条件就是满足块数大于等于k的x的最大值
我们分情况来判断,假如x从小到大递增
如果中间值 x m i d x_{mid} xmid大于等于k是成立的,说明说明,比中间值小的所有数字,都是满足条件的,因此我们就要让左边界更新为中心值
示例代码
#include<iostream>
using namespace std;const int N = 1e5 + 10;int n, k;
int h[N], w[N]; // 分别代表每一块的高度和宽度bool check(int mid) // 判断块数是否大于k
{int res = 0; // 一共可以分成多少块for (int i = 0; i < n; i++){res += (w[i] / mid) * (h[i] / mid); // 注意括号if (res >= k)return true;}return false;
}
int main()
{cin >> n >> k;for (int i = 0; i < n; i++)cin >> h[i] >> w[i];int l = 1, r = 1e5;while (l < r){int mid = (l + r + 1) / 2;if (check(mid))l = mid;elser = mid - 1;}cout << r << '\n';return 0;
}
相关文章:

每日算法打卡:分巧克力 day 9
文章目录 原题链接题目描述输入格式输出格式数据范围输入样例:输出样例: 题目分析示例代码 原题链接 1227. 分巧克力 题目难度:简单 题目来源:第八届蓝桥杯省赛C A/B组,第八届蓝桥杯省赛Java A/B/C组 题目描述 儿童节那天有 …...
Golang switch 语句
简介 switch 语句提供了一种简洁的方式来执行多路分支选择 基本使用 基本语法如下: switch expression { case value1:// 当 expression 的值等于 value1 时执行 case value2:// 当 expression 的值等于 value2 switch 的每个分支自动提供了隐式的 break&#x…...

可碧教你C++——位图
本章节是哈希的延申 可碧教你C——哈希http://t.csdnimg.cn/3R8TU 一文详解C——哈希 位图 位图是基于哈希表的原理产生的一种新的container——bitset 基于哈希映射的原理,我们在查找的时候,可以直接去定址到元素的具体位置,然后直接访问该…...

2024年虚拟DOM技术将何去何从?
从诞生之初谈起,从命令式到声明式,Web开发的演变之路 Web开发的起源与jQuery的统治 在Web开发的早期阶段,操作DOM元素主要依赖命令式编程。当时,jQuery因其易用性而广受欢迎。使用jQuery,开发者通过具体的命令操作DOM&…...
基于51单片机的恒温淋浴器控制电路设计
标题:基于51单片机的智能恒温淋浴器控制系统设计与实现 摘要: 本论文主要探讨了一种基于STC89C51单片机为核心控制器的恒温淋浴器控制系统的详细设计与实现。系统通过集成温度传感器实时监测水温,结合PID算法精确控制加热元件工作状态&#…...
【redis】redis的bind配置
在配置文件redis.conf中,默认的bind 接口是127.0.0.1,也就是本地回环地址。这样的话,访问redis服务只能通过本机的客户端连接,而无法通过远程连接, 这样可以避免将redis服务暴露于危险的网络环境中,防止一些…...

C++ 继承
目录 一、继承的概念及定义 1、继承的概念 2、继承定义 二、基类和派生类对象赋值转换 三、继承中的作用域 四、派生类的默认成员函数 五、继承与友元 六、继承与静态成员 七、复杂的菱形继承及菱形虚拟继承 1、菱形继承 2、虚拟继承 3、例题 八、继承的总结和反思…...

了解ASP.NET Core 中的文件提供程序
写在前面 ASP.NET Core 通过文件提供程序来抽象化文件系统访问。分为物理文件提供程序(PhysicalFileProvider)和清单嵌入的文件提供程序(ManifestEmbeddedFileProvider)还有复合文件提供程序(CompositeFileProvider );其中PhysicalFileProvider 提供对物理文件系统…...

竞赛保研 基于深度学习的人脸性别年龄识别 - 图像识别 opencv
文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 毕业设计…...
JavaScript音视频,JavaScript简单获取电脑摄像头画面并播放
前言 本章实现JavaScript简单获取电脑摄像头画面并播放的功能 兼容性(不支持Node.js) 需要注意的是,由于涉及到用户的隐私和安全,获取用户媒体设备需要用户的明确同意,并且可能需要在用户的浏览器中启用相关的权限。在某些浏览器中,可能需要用户手动开启摄像头权限。 …...
《JVM由浅入深学习【五】 2024-01-08》JVM由简入深学习提升分享
目录 JVM何时会发生堆内存溢出?1. 堆内存溢出的定义2. 内存泄漏的原因3. 堆内存溢出的常见场景4. JVM参数调优5. 实际案例分析 JVM如何判断对象可以回收1.可达性分析的基本思路2.实际案例3.可以被回收的对象4.拓展, 谈谈 Java 中不同的引用类型? 结语感…...

FastDFS之快速入门、上手
知识概念 分布式文件系统 通过计算机网络将各个物理存储资源连接起来。通过分布式文件系统,将网络上任意资源以逻辑上的树形结构展现,让用户访问网络上的共享文件更见简便。 文件存储的变迁: 直连存储:直接连接与存储…...

Vue 中的 ref 与 reactive:让你的应用更具响应性(中)
🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云…...

【数据库基础】Mysql与Redis的区别
看到一篇不错的关于“Mysql与Redis的区别”的文章,转过来记录下~ 文章目录 一、数据库类型二、运行机制三、什么是缓存数据库呢?四、优缺点比较五、区别总结六、数据可以全部直接用Redis储存吗?参考资料 一、数据库类型 Redis:NOS…...

JVM工作原理与实战(六):类的生命周期-连接阶段
专栏导航 JVM工作原理与实战 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、类的生命周期 1.加载(Loading) 2.连接(Linking) 3.初始化(Initialization) 4.使用(Using&…...
【OCR】 - Tesseract OCR在Windows系统中安装
Tesseract OCR 在Windows环境下安装Tesseract OCR(Optical Character Recognition)通常包括以下几个步骤: 下载Tesseract 访问Tesseract的GitHub发布页面:https://github.com/tesseract-ocr/tesseract/releases找到适合你操作系…...

YOLOv8改进 | 损失函数篇 | SlideLoss、FocalLoss分类损失函数助力细节涨点(全网最全)
一、本文介绍 本文给大家带来的是分类损失 SlideLoss、VFLoss、FocalLoss损失函数,我们之前看那的那些IoU都是边界框回归损失,和本文的修改内容并不冲突,所以大家可以知道损失函数分为两种一种是分类损失另一种是边界框回归损失,上一篇文章里面我们总结了过去百分之九十的…...
计算机网络试题——填空题(附答案)
在OSI模型中,第一层是____________层。 答案:物理(Physical) TCP协议是一种_____________连接的协议。 答案:面向连接(Connection-oriented) IPv6地址的位数是____________。 答案:1…...

第二证券:股票私募仓位指数创近八周新高
1月8日,A股几大首要指数全线收跌,上证指数收于日内最低点2887.54点,间隔上一年5月份的阶段高点3418.95点现已跌去了15.54%。 不过,虽然商场仍未清晰止跌,私募基金们却现已进场“抄底”。私募排排网最新发布的私募仓位…...
35-javascript基础,引入方式;变量命名规范
html分为三部分;结构html,表现css,行为js;js就是javascript js包含三部分: ECMAScript:简称ES,ES5,ES6核心语法 DOM:获取和操作html元素的标准方法;BOM&am…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...