每日算法打卡:分巧克力 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…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...