当前位置: 首页 > news >正文

每日算法打卡:分巧克力 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 块巧克力分给小朋友们。

切出的巧克力需要满足:

  1. 形状是正方形,边长是整数
  2. 大小相同

例如一块 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 1N,K105,
1 ≤ H i , W i ≤ 1 0 5 1 \le H_i,W_i \le 10^5 1Hi,Wi105

输入样例:
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

这样,我们就可以看出来,块数是和边长一定是一个递减的函数关系

屏幕截图 2024-01-09 105806.png

我们需要找到一个个数大于等于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

文章目录 原题链接题目描述输入格式输出格式数据范围输入样例&#xff1a;输出样例&#xff1a; 题目分析示例代码 原题链接 1227. 分巧克力 题目难度&#xff1a;简单 题目来源&#xff1a;第八届蓝桥杯省赛C A/B组,第八届蓝桥杯省赛Java A/B/C组 题目描述 儿童节那天有 …...

Golang switch 语句

简介 switch 语句提供了一种简洁的方式来执行多路分支选择 基本使用 基本语法如下&#xff1a; switch expression { case value1:// 当 expression 的值等于 value1 时执行 case value2:// 当 expression 的值等于 value2 switch 的每个分支自动提供了隐式的 break&#x…...

可碧教你C++——位图

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

2024年虚拟DOM技术将何去何从?

从诞生之初谈起&#xff0c;从命令式到声明式&#xff0c;Web开发的演变之路 Web开发的起源与jQuery的统治 在Web开发的早期阶段&#xff0c;操作DOM元素主要依赖命令式编程。当时&#xff0c;jQuery因其易用性而广受欢迎。使用jQuery&#xff0c;开发者通过具体的命令操作DOM&…...

基于51单片机的恒温淋浴器控制电路设计

标题&#xff1a;基于51单片机的智能恒温淋浴器控制系统设计与实现 摘要&#xff1a; 本论文主要探讨了一种基于STC89C51单片机为核心控制器的恒温淋浴器控制系统的详细设计与实现。系统通过集成温度传感器实时监测水温&#xff0c;结合PID算法精确控制加热元件工作状态&#…...

【redis】redis的bind配置

在配置文件redis.conf中&#xff0c;默认的bind 接口是127.0.0.1&#xff0c;也就是本地回环地址。这样的话&#xff0c;访问redis服务只能通过本机的客户端连接&#xff0c;而无法通过远程连接&#xff0c; 这样可以避免将redis服务暴露于危险的网络环境中&#xff0c;防止一些…...

C++ 继承

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

了解ASP.NET Core 中的文件提供程序

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

竞赛保研 基于深度学习的人脸性别年龄识别 - 图像识别 opencv

文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 毕业设计…...

JavaScript音视频,JavaScript简单获取电脑摄像头画面并播放

前言 本章实现JavaScript简单获取电脑摄像头画面并播放的功能 兼容性(不支持Node.js) 需要注意的是,由于涉及到用户的隐私和安全,获取用户媒体设备需要用户的明确同意,并且可能需要在用户的浏览器中启用相关的权限。在某些浏览器中,可能需要用户手动开启摄像头权限。 …...

《JVM由浅入深学习【五】 2024-01-08》JVM由简入深学习提升分享

目录 JVM何时会发生堆内存溢出&#xff1f;1. 堆内存溢出的定义2. 内存泄漏的原因3. 堆内存溢出的常见场景4. JVM参数调优5. 实际案例分析 JVM如何判断对象可以回收1.可达性分析的基本思路2.实际案例3.可以被回收的对象4.拓展&#xff0c; 谈谈 Java 中不同的引用类型? 结语感…...

FastDFS之快速入门、上手

知识概念 分布式文件系统 通过计算机网络将各个物理存储资源连接起来。通过分布式文件系统&#xff0c;将网络上任意资源以逻辑上的树形结构展现&#xff0c;让用户访问网络上的共享文件更见简便。 文件存储的变迁&#xff1a; 直连存储&#xff1a;直接连接与存储&#xf…...

Vue 中的 ref 与 reactive:让你的应用更具响应性(中)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…...

【数据库基础】Mysql与Redis的区别

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

JVM工作原理与实战(六):类的生命周期-连接阶段

专栏导航 JVM工作原理与实战 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、类的生命周期 1.加载&#xff08;Loading&#xff09; 2.连接&#xff08;Linking&#xff09; 3.初始化&#xff08;Initialization&#xff09; 4.使用&#xff08;Using&…...

【OCR】 - Tesseract OCR在Windows系统中安装

Tesseract OCR 在Windows环境下安装Tesseract OCR&#xff08;Optical Character Recognition&#xff09;通常包括以下几个步骤&#xff1a; 下载Tesseract 访问Tesseract的GitHub发布页面&#xff1a;https://github.com/tesseract-ocr/tesseract/releases找到适合你操作系…...

YOLOv8改进 | 损失函数篇 | SlideLoss、FocalLoss分类损失函数助力细节涨点(全网最全)

一、本文介绍 本文给大家带来的是分类损失 SlideLoss、VFLoss、FocalLoss损失函数,我们之前看那的那些IoU都是边界框回归损失,和本文的修改内容并不冲突,所以大家可以知道损失函数分为两种一种是分类损失另一种是边界框回归损失,上一篇文章里面我们总结了过去百分之九十的…...

计算机网络试题——填空题(附答案)

在OSI模型中&#xff0c;第一层是____________层。 答案&#xff1a;物理&#xff08;Physical&#xff09; TCP协议是一种_____________连接的协议。 答案&#xff1a;面向连接&#xff08;Connection-oriented&#xff09; IPv6地址的位数是____________。 答案&#xff1a;1…...

第二证券:股票私募仓位指数创近八周新高

1月8日&#xff0c;A股几大首要指数全线收跌&#xff0c;上证指数收于日内最低点2887.54点&#xff0c;间隔上一年5月份的阶段高点3418.95点现已跌去了15.54%。 不过&#xff0c;虽然商场仍未清晰止跌&#xff0c;私募基金们却现已进场“抄底”。私募排排网最新发布的私募仓位…...

35-javascript基础,引入方式;变量命名规范

html分为三部分&#xff1b;结构html&#xff0c;表现css&#xff0c;行为js&#xff1b;js就是javascript js包含三部分&#xff1a; ECMAScript&#xff1a;简称ES&#xff0c;ES5&#xff0c;ES6核心语法 DOM&#xff1a;获取和操作html元素的标准方法&#xff1b;BOM&am…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 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…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...