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

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...