当前位置: 首页 > 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" ---全局…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...