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

蓝桥杯第八届A组:分巧克力

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 NN 块巧克力,其中第 ii 块是 Hi×WiHi​×Wi 的方格组成的长方形。为了公平起见,

小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足:

  1. 形状是正方形,边长是整数;

  2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

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

输入描述

第一行包含两个整数 N,KN,K (1≤N,K≤1051≤N,K≤105)。

以下 N 行每行包含两个整数 Hi,WiHi​,Wi​ (1≤Hi,Wi≤1051≤Hi​,Wi​≤105)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

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

输入输出样例

示例

输入

2 10
6 5
5 6

输出

2

运行限制

  • 最大运行时间:2s
  • 最大运行内存: 256M

总通过次数: 10390  |  总提交次数: 11980  |  通过率: 86.7%

难度: 困难   标签: 2017, 省赛, 二分

思路:

定义bool型的判断函数,判断把每块巧克力切后的块数相加是否符合小朋友的要求,即大于等于K

然后用二分法寻找即可

代码:

​​#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
const int N=1e5+10;
int h[N],w[N];
int n,k;
bool count(int m)
{int res=0;for(int i=1;i<=n;i++){res+=(h[i]/m)*(w[i]/m);if(res>=k) return true;}return false;
}
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d%d",&h[i],&w[i]);int l=1,r=1e5;while(l<r){int mid=(l+r+1)/2;if(count(mid)) l=mid;else r=mid-1;}printf("%d",l);return 0;
}[点击并拖拽以移动]
​[点击并拖拽以移动]
​

相关文章:

蓝桥杯第八届A组:分巧克力

题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 NN 块巧克力&#xff0c;其中第 ii 块是 HiWiHi​Wi 的方格组成的长方形。为了公平起见&#xff0c; 小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克…...

前端框架的发展史介绍框架特点

目录 1.前端框架的发展历程 2.官网、优缺点、使用场景 2.1 jQuery 2.2 AngularJS 2.3 React 2.4 Vue.js 2.5 Angular 1.前端框架的发展历程 jQuery&#xff08;2006年&#xff09;&#xff1a;jQuery是一个非常流行的JavaScript库&#xff0c;用于简化DOM操作和事件处理…...

【MatLab】之:Simulink安装

一、内容简介 本文介绍如何在 MatLab 中安装 Simulink 仿真工具包。 二、所需原材料 MatLab R2020b&#xff08;教学使用&#xff09; 三、安装步骤 1. 点击菜单中的“附加功能”&#xff0c;进入附加功能管理器&#xff1a; 2. 在左侧的“按类别筛选”下选择Using Simulin…...

动手学习深度学习之环境配置

创建conda虚拟环境 下载anaconda&#xff0c;安装到计算机&#xff0c;修改镜像源到国内 show_channel_urls: true channels:- https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/pytorch/- http://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main/- http://mirrors.tu…...

【机器学习300问】35、什么是随机森林?

〇、让我们准备一些训练数据 idx0x1x2x3x4y04.34.94.14.75.5013.96.15.95.55.9022.74.84.15.05.6036.64.44.53.95.9146.52.94.74.66.1152.76.74.25.34.81 表格中的x0到x4一共有5个特征&#xff0c;y是目标值只有0,1两个值说明是一个二分类问题。 关于决策树相关的前置知识&am…...

用云服务器构建gpt和stable-diffusion大模型

用云服务器构建gpt和stable-diffusion大模型 一、前置知识二、用云端属于自己的聊天chatGLM3step1、项目配置step2、环境配置1、前置知识2、环境配置流程 step3、创建镜像1、前置知识2、创建镜像流程 step4、通过 Gradio 创建ChatGLM交互界面1、前置知识2、创建ChatGLM交互界面…...

备考2024年小学生古诗文大会:历年真题15题练习和独家解析

最近有家长在问如何提高小学生古诗词的知识&#xff1f;如何激发小学生古诗词的学习兴趣&#xff1f;如何提高小学古诗词的学习成绩&#xff1f;如何备考2024年小学生古诗文大会&#xff1f;...我的建议是参加每年一度的小学生古诗词大会&#xff08;免费参加&#xff0c;无参赛…...

C++之模板

本阶段主要针对C泛型编程和ST技术做详细讲解&#xff0c;探讨C更深层的使用 1.1 模板的概念 模板就是建立通用的模具&#xff0c;大大提高复用性 模板的特点: 模板不可以直接使用&#xff0c;它只是一个框架 模板的通用并不是万能的 1.2 函数模板 C另一种编程思想称为 …...

Ubuntu Flask 运行 gunicorn+Nginx 部署

linux Ubuntu 下运行python 程序出现killed 原因&#xff1a;CPU或内存限制&#xff1a;在华为云上&#xff0c;你可能有CPU或内存使用的限制。例如&#xff0c;如果你使用的是一个固定大小的实例&#xff0c;那么超过该实例的CPU或内存限制可能会导致进程被杀死。 参考&am…...

Tuxera NTFS 2023安装使用教程 Tuxera NTFS破解版 Tuxera NTFS for Mac优惠

对于必须在Windows电脑和Mac电脑之间来回切换的Mac朋友来说&#xff0c;跨平台不兼容一直是一个巨大的障碍&#xff0c;尤其是当我们需要使用NTFS格式的硬盘在Windows和macOS之间共享文件时。因为Mac默认不支持写入NTFS磁盘。 为了解决这一问题&#xff0c;很多朋友会选择很便捷…...

Linux-centos如何搭建yum源仓库

1.本地搭建&#xff08;无需连接外网&#xff09; 1.1检查网络配置&#xff0c;及网络连接 打开虚拟机&#xff0c;点击【编辑——虚拟网络编辑器】 点击【仅主机模式】查看子网段是否和局内IP匹配 进入局内&#xff0c;查看网络IP是否在你上述设置的网段内&#xff0c;如果不…...

Vue组件中引入jQuery

两种在vue中引入jQuery的方式 1、普通html中使用jQuery 将jQuer的文件导入到项目中&#xff0c;然后直接使用<script src"jQuery.js"></script>即可。 <script src"jQuery.js"></script> 2、vue组件中使用jQuery 安装依赖 c…...

设计模式 --3:装扮模式

结构图 代码 #include<iostream>using namespace std;class person { public:person() {};person(string name) { this->name name; }virtual void show() {cout << "装扮的:" << this->name << endl;} private:string name; }; //装…...

element-plus中的表单校验

1. 简单校验&#xff1a; 1.1 在script中给出校验规则对象&#xff0c;主要属性名与form对象的属性名一致1.2 一个字段的校验规则可以有多个&#xff0c;值是一个数组&#xff0c;数组中的一个对象就是一条校验规则1.3 主要校验规则&#xff1a; 1.3.1 required&#xff1a;是…...

ros小问题之roslaunch tab补不全新增的功能包

在学习Gazebo这一章节时&#xff0c;通过catkin_create_pkg命令创建了仿真机械臂所需的软件包&#xff0c;创建完成后里面的内容直接拷贝了教材配套的文件&#xff0c;但在roslaunch时&#xff0c;摁tab键补不全新加的包。 重新source catkin_ws/devel/setup.bash不起作用&…...

C#常见的.Net类型(二)

目录 一、在集合中存储多个对象理解集合的选择1.列表2.字典3.堆栈4.队列5.集 二、使用Span、索引和范围Span索引范围 处理类型和属性1.特性2.创建自定义特性3.反射 一、在集合中存储多个对象 处理集合的常见类型 类型描述List动态大小的数组&#xff0c;可以按索引访问Dictio…...

oracle临时表空间不释放

项目报错 nested exception is java.sql.SQLException: ORA-01652: unable to extend temp segment by 128 in tablespace TEMP 原因是临时表空间满了&#xff0c;临时表空间一直增长&#xff0c;未释放导致临时表空间使用率100%。 查询临时表空间使用率 --临时表空间利用率…...

Chapter 13 Techniques of Design-Oriented Analysis: The Feedback Theorem

Chapter 13 Techniques of Design-Oriented Analysis: The Feedback Theorem 从这一章开始讲负反馈Control系统和小信号建模. 13.2 The Feedback Theorem 首先介绍 Middlebrook’s Feedback Theorem 考虑下面负反馈系统 传输函数 Guo/ui G ( s ) u o u i G ∞ T 1 T G…...

科研学习|论文解读——美国政治经济中的权力:网络分析(JASIST, 2019)

论文原题目 Power in the U.S. political economy: A network analysis 摘要 美国政治经济的许多特征产生于大型政治和经济机构之间的互动&#xff0c;然而我们对它们的互动性质和这些机构之间的权力分配知之甚少。在本文中&#xff0c;对总部设在美国的组织的网络进行了详细的…...

常用的git命令

一、常用的git命令 1. 配置 git config --local user.name "xxx" ---仅对当前Git仓库有效。配置信息将保存在当前Git仓库的 .git/config 文件中 local优先级最高&#xff0c;会覆盖其他范围的相同配置 git config --global user.email "xxx" ---全局…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...