问题 F: 分巧克力
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力,其中第i 块Hi×Wi 的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足:
- 形状是正方形,边长是整数;
- 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?
输入
第一行包含两个整数 N,K 1≤N,K≤105)。
以下 N 行每行包含两个整数 H_i,W_i (1≤Hi,Wi≤105)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10 6 5 5 6
样例输出
2
问题分析
-
切割条件:
从每块巧克力中切割的正方形必须边长相等。每块巧克力可以切割出不同数量的正方形,数量取决于其尺寸和正方形的边长。 -
搜索范围:
最大可能的正方形边长不会超过所有巧克力尺寸中最小的一边。二分查找可以用来高效地搜索最大边长。 -
计算方法:
对于每一个可能的边长,计算所有巧克力块总共能切割出多少个这样的正方形。如果对于某个边长可以切割出的总数大于或等于 K,则该边长是可行的。 -
优化目标:
在满足至少切割出 K 块的条件下,找到最大的边长。 -
实现策略:
使用二分查找方法在可能的边长范围内寻找最优解。
#include <bits/stdc++.h>
using namespace std;// 定义一个函数,用于计算当前边长下可以切割出多少块巧克力
int sum(vector<pair<int,int>>& a, int mid) {int t = 0;for (auto &k : a) { // k为a中每一次取出的元素,类型是pair<int,int>类型t += (k.first / mid) * (k.second / mid); // 计算每块巧克力可以切割出多少块大小为 mid x mid 的巧克力}return t; // 返回总共可以切割出的巧克力块数
}// 定义一个函数,用于找出最大的可以切割出的巧克力边长
int dx(vector<pair<int,int>>& a, int n, int k) {int l = 1, r = 1e5, mid, ans = 0;while (l <= r) {mid = (l + r) / 2; // 计算中间值if (sum(a, mid) >= k) { // 如果可以切割出足够多的巧克力块ans = mid; // 更新答案l = mid + 1; // 尝试更大的边长} else {r = mid - 1; // 尝试更小的边长}}return ans; // 返回最大的可以切割出的巧克力边长
}int main() {int n, k;cin >> n >> k; // 读取巧克力块数和需要的巧克力块数vector<pair<int,int>> a(n); // 创建一个动态数组来存储每块巧克力的尺寸for (int i = 0; i < n; i++) {cin >> a[i].first >> a[i].second; // 读取每块巧克力的尺寸}cout << dx(a, n, k); // 输出最大的可以切割出的巧克力边长
}
相关文章:
问题 F: 分巧克力
题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力,其中第i 块HiWi 的方格组成的长方形。 为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。 切出的巧克力需要满足&am…...
安装pillow可能遇到的问题
安装命令 pip install Pillow安装 Pillow 这个 Python 图像处理库时可能会遇到多种问题。以下一些常见的安装问题及其解决方法: 缺少依赖项: Pillow 安装可能需要一些基础库,如 libjpeg 和 zlib。如果在安装时提示缺少这些库,你需要先安装它…...
详解ajax、fetch、axios的区别
众所周知它们都用来发送请求,其实它们区别还蛮大的。这也是面试中的高频题,本文将详细进行讲解。 1. ajax 英译过来是Aysnchronous JavaScript And XML,直译是异步JS和XML(XML类似HTML,但是设计宗旨就为了传输数据&a…...
致远OA getAjaxDataServlet XXE漏洞复现(QVD-2023-30027)
0x01 产品简介 致远互联-OA 是数字化构建企业数字化协同运营中台,面向企业各种业务场景提供一站式大数据分析解决方案的协同办公软件。 0x02 漏洞概述 致远互联-OA getAjaxDataServlet 接口处存在XML实体注入漏洞,未经身份认证的攻击者可以利用此漏洞读取系统内部敏感文件…...
力扣最热一百题——只出现一次的数字
这个合集已经很久没有更新了,今天来更新更新~~~ 目录 力扣题号 题目 题目描述 示例 提示 题解 Java解法一:Map集合 Java解法二:位运算 C位运算代码 力扣题号 136. 只出现一次的数字 - 力扣(LeetCode) 下述题…...
UE5 UE4 修复GPU驱动程序崩溃
原贴链接:https://mp.weixin.qq.com/s/e5l9XtfwEFWgwhHi1b2idg UE5 UE4在处理含有大量图形的项目时,你有可能会遇到GPU崩溃 可以通过修改注册表,修复崩溃。 GPU崩溃情况概述 UE5 UE4在处理含有大量图形的项目时,你有可能会遇到G…...
SpiderFlow爬虫平台 前台RCE漏洞复现(CVE-2024-0195)
0x01 产品简介 SpiderFlow是新一代爬虫平台,以图形化方式定义爬虫流程,以流程图的方式定义爬虫,不写代码即可完成爬虫,是一个高度灵活可配置的爬虫平台。 0x02 漏洞概述 SpiderFlow爬虫平台src/main/java/org/spiderflow/controller/FunctionController.java文件的Functi…...
帆软report 设置条件属性,值为负数标为红色功能时,不生效
详细情况: 在设置负数为红色功能前,已经有一个条件属性,数据集获取的值为空或者为0时,转换成 - 符号。如下图: 具体表单显示效果如下: 条件属性2设置 原因 因为条件属性1设置的 - 符号没有设置颜色…...
QML实现的图片浏览器
很久之前实现了一个QWidget版本的图片浏览器:基于Qt5的图片浏览器QHImageViewer 今天用QML也实现一个,功能差不多: ●悬浮工具栏 ●支持图片缩放、旋转、还原、旋转、拖动。 ●拖动图片时,释放鼠标图片会惯性滑动。 ●支持左右翻页查看文件夹中的图片。 ●支持保存图片至本…...
【HTML】对字体的所有操作详解(经典)
目录 一、文字样式设置的基本标签二 、 设置文字的颜色三、设置文字的尺寸四、 设置文字的字体五、 使文字倾斜六、 使文字加粗七、处理网页中的特殊字符十、 如何更方便地忽略浏览器对部分HTML的解析十一、 其他文字修饰方法十二、为了让文字富有变化,或者为了着意…...
关于调查项目的讨论
怎么安排一个调查项目 要安排一个调查项目,你需要经过以下步骤: 1. 确定调查目的:明确你为什么要进行这个调查,你想了解什么问题或获得什么信息。 2. 制定研究问题:根据调查目的,确定需要回答的具体问题…...
Matlab三维绘图
绘制三维图plot3 t0:pi/50:10*pi; xsin(t); ycos(t); zt; plot3(x,y,z); 产生栅格数据点meshgrid 这个接口在绘制三维图像里面相当重要,很多时候要将向量变成矩阵才能绘制三维图。 x0:0.5:5; y0:1:10; [X,Y]meshgrid(x,y); plot(X,Y,o); x和y是向量,…...
一体式气象站的优点是什么?带大家了解一下
一体式气象站是一款高度集成、低功耗、可快速安装、便于野外监测使用的高精度自动气象观测设备。 一体式气象站的优点主要体现在以下几个方面: 集成度高:一体式气象站集成了多种气象传感器、数据处理单元、显示单元和通讯模块等,可以同时监…...
第八讲_css定位
css定位 1. css定位介绍2. 静态定位(static)3. 相对定位(relative)4. 绝对定位(absolute)5. 固定定位(fixed)6. 粘性定位(sticky) 1. css定位介绍 在 css 中…...
找出字符串中第一个匹配项的下标(Leetcode28)
例题: 分析: 题目的意思就是: 先给出一个字符串pattern,要拿着pattern字符串和原始字符串(origin)比对,若在origin中找到了pattern字符串,则返回pattern字符串在原始字符串origin中的…...
【分布式微服务专题】从单体到分布式(四、SpringCloud整合Sentinel)
目录 前言阅读对象阅读导航前置知识一、什么是服务雪崩1.1 基本介绍1.2 解决方案 二、什么是Sentinel2.1 基本介绍2.2 设计目的2.3 基本概念 三、Sentinel 功能和设计理念3.1 流量控制3.2 熔断降级3.3 系统负载保护 四、Sentinel 是如何工作的 笔记正文一、简单整合Sentinel1.1…...
RHCE9学习指南 第19章 网络时间服务器
19.1 时间同步的必要性 对于一些服务来说对时间要求非常严格,例如,图19-1所示由三台服务器搭建的ceph集群。 图19-1 三台机器搭建的集群对时间要求比较高 这三台服务器的时间必须要保持一样,如果不一样,就会显示报警信息。那么…...
大模型 RAG 问答技术架构及核心模块盘点:从 Embedding、prompt-embedding 到 Reranker
对于RAG而言,2023年已经出现了很多工作,草台班子有了一堆,架构也初步走通,2024年应该会围绕搜索增强做更多的优化工作。 因此我们今天来系统回顾下RAG中的模块,包括一些架构,文本嵌入embedding等ÿ…...
基于Selenium+Python的web自动化测试框架
一、什么是Selenium? Selenium是一个基于浏览器的自动化测试工具,它提供了一种跨平台、跨浏览器的端到端的web自动化解决方案。Selenium主要包括三部分:Selenium IDE、Selenium WebDriver 和Selenium Grid。 Selenium IDE:Firefo…...
LeetCode刷题--- 地下城游戏
个人主页:元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.csdnimg.cn/hKh2l 前言:这个专栏主要讲述动…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
