蓝桥杯第八届A组:分巧克力
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力,其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。为了公平起见,
小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足:
-
形状是正方形,边长是整数;
-
大小相同;
例如一块 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 块巧克力,其中第 ii 块是 HiWiHiWi 的方格组成的长方形。为了公平起见, 小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克…...

前端框架的发展史介绍框架特点
目录 1.前端框架的发展历程 2.官网、优缺点、使用场景 2.1 jQuery 2.2 AngularJS 2.3 React 2.4 Vue.js 2.5 Angular 1.前端框架的发展历程 jQuery(2006年):jQuery是一个非常流行的JavaScript库,用于简化DOM操作和事件处理…...

【MatLab】之:Simulink安装
一、内容简介 本文介绍如何在 MatLab 中安装 Simulink 仿真工具包。 二、所需原材料 MatLab R2020b(教学使用) 三、安装步骤 1. 点击菜单中的“附加功能”,进入附加功能管理器: 2. 在左侧的“按类别筛选”下选择Using Simulin…...
动手学习深度学习之环境配置
创建conda虚拟环境 下载anaconda,安装到计算机,修改镜像源到国内 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个特征,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题练习和独家解析
最近有家长在问如何提高小学生古诗词的知识?如何激发小学生古诗词的学习兴趣?如何提高小学古诗词的学习成绩?如何备考2024年小学生古诗文大会?...我的建议是参加每年一度的小学生古诗词大会(免费参加,无参赛…...

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

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

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

Linux-centos如何搭建yum源仓库
1.本地搭建(无需连接外网) 1.1检查网络配置,及网络连接 打开虚拟机,点击【编辑——虚拟网络编辑器】 点击【仅主机模式】查看子网段是否和局内IP匹配 进入局内,查看网络IP是否在你上述设置的网段内,如果不…...

Vue组件中引入jQuery
两种在vue中引入jQuery的方式 1、普通html中使用jQuery 将jQuer的文件导入到项目中,然后直接使用<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. 简单校验: 1.1 在script中给出校验规则对象,主要属性名与form对象的属性名一致1.2 一个字段的校验规则可以有多个,值是一个数组,数组中的一个对象就是一条校验规则1.3 主要校验规则: 1.3.1 required:是…...

ros小问题之roslaunch tab补不全新增的功能包
在学习Gazebo这一章节时,通过catkin_create_pkg命令创建了仿真机械臂所需的软件包,创建完成后里面的内容直接拷贝了教材配套的文件,但在roslaunch时,摁tab键补不全新加的包。 重新source catkin_ws/devel/setup.bash不起作用&…...
C#常见的.Net类型(二)
目录 一、在集合中存储多个对象理解集合的选择1.列表2.字典3.堆栈4.队列5.集 二、使用Span、索引和范围Span索引范围 处理类型和属性1.特性2.创建自定义特性3.反射 一、在集合中存储多个对象 处理集合的常见类型 类型描述List动态大小的数组,可以按索引访问Dictio…...

oracle临时表空间不释放
项目报错 nested exception is java.sql.SQLException: ORA-01652: unable to extend temp segment by 128 in tablespace TEMP 原因是临时表空间满了,临时表空间一直增长,未释放导致临时表空间使用率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 摘要 美国政治经济的许多特征产生于大型政治和经济机构之间的互动,然而我们对它们的互动性质和这些机构之间的权力分配知之甚少。在本文中,对总部设在美国的组织的网络进行了详细的…...
常用的git命令
一、常用的git命令 1. 配置 git config --local user.name "xxx" ---仅对当前Git仓库有效。配置信息将保存在当前Git仓库的 .git/config 文件中 local优先级最高,会覆盖其他范围的相同配置 git config --global user.email "xxx" ---全局…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...