2024/3/11打卡分巧克力(第8届蓝桥杯省赛)——二分

news/2024/5/26 21:03:56/文章来源:https://blog.csdn.net/weixin_63001635/article/details/136625961

题目

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足:

  1. 形状是正方形,边长是整数
  2. 大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

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

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

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

输出格式

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

数据范围

1≤N,K≤10^5,
1≤Hi,Wi≤10^5

 输入样例:
2 10
6 5
5 6
输出样例:
2

思路:

第一个问题,每块巧克力最大可以分成边长为多少的正方形?

        假设巧克力的大小为 w\times h

        那么每个巧克力最大可以被分为 h\times h\ \ (h<=w) 或者 w\times w\ \ (w<=h) 大小。

一个 w\times h 大小的巧克力最多可以被分成多少个 x\times x 大小的巧克力?

        (h/x)*(w/x) 块,行数除以 x 向下取整 则是能在行上最多能分到的最多的块数,同理列,那么在行数上能分得的最多块数 * 列上能分得的最多块数就是一块巧克力能被分得的最多的块数。

        因此,我们只需要取所有巧克力中长度的最大值max,从1枚举到max,就可以找出能够分得的最大块数。(使用二分代替枚举   O(n)->O(logn))

代码

import java.io.*;class Main{static int N = 100010;static int n,k;static int[] h = new int[N];static int[] w = new int[N];public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String[] s = in.readLine().split(" ");n = Integer.parseInt(s[0]);k = Integer.parseInt(s[1]);int max = 0; // 应该取max,而不是min,有些巧克力小但是可以不用for(int i=0;i<n;i++){s = in.readLine().split(" ");h[i] = Integer.parseInt(s[0]);w[i] = Integer.parseInt(s[1]);max = Math.max(max,h[i]);max = Math.max(max,w[i]);}int l = 1,r = max; // 取0是因为r=max可能为1,进不去while.好像也可以,输入保证了每个都可以分得1*1while(l<r){int mid = l+r+1>>1;if(check(mid)) l = mid;else r = mid-1;}System.out.println(r);}public static boolean check(int u){ // 判断如果要分成u*u可不可以int count = 0;for(int i=0;i<n;i++){ // 计算所有能分成u*u的巧克力快数count += (w[i]/u)*(h[i]/u);}if(count<k) return false; // 不够分else return true;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1006729.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

面试题:Redis 为什么读写性能高?

Redis 的速度⾮常快&#xff0c;单机的 Redis 就可以⽀撑每秒十几万的并发&#xff0c;性能是 MySQL 的⼏⼗倍。速度快的原因主要有⼏点&#xff1a; 基于内存的数据存储 Redis 将数据存储在内存当中&#xff0c;使得数据的读写操作避开了磁盘 I/O。而内存的访问速度远超硬盘&a…

数据处理分类、数据仓库产生原因

个人看书学习心得及日常复习思考记录&#xff0c;个人随笔。 数据处理分类 操作型数据处理&#xff08;基础&#xff09; 操作型数据处理主要完成数据的收集、整理、存储、查询和增删改操作等&#xff0c;主要由一般工作人员和基层管理人员完成。 联机事务处理系统&#xff…

opengl日记27-opengl报错ERROR::SHADER::PROGRAM::LINKING_FAILED

Author: wencoo Blog&#xff1a;https://wencoo.blog.csdn.net/ Date: 14/03/2024 Email: jianwen056aliyun.com Wechat&#xff1a;wencoo824 QQ&#xff1a;1419440391 Details:文章目录 目录正文 或 背景 报错信息ERROR::SHADER::PROGRAM::LINKING_FAILED解决方法情况1情况…

SpringController返回值和异常自动包装

今天遇到一个需求&#xff0c;在不改动原系统代码的情况下。将Controller的返回值和异常包装到一个统一的返回对象中去。 例如原系统的接口 public String myIp(ApiIgnore HttpServletRequest request);返回的只是一个IP字符串"0:0:0:0:0:0:0:1"&#xff0c;目前接口…

PandasAI—让AI做数据分析

安装 pip install pandasai !pip install --upgrade pandas pandasai 导入依赖项 import pandas as pdfrom pandasai import PandasAIfrom pandasai.llm.openai import OpenAI使用pandas创建一个数据框 df pd.DataFrame({"country": ["United States",…

如何解决ChatGPT消息发不出问题,GPT消息无法发出去,没有响应的问题

前言 今天工作到一半&#xff0c;登陆ChatGPT想咨询一些代码上的问题&#xff0c;结果发现发不了消息了。 ChatGPT 无法发送消息&#xff0c;但是能查看历史的对话。不过首先可以先打开官方的网站&#xff1a;https://status.openai.com/ 。 查看当前Open AI的状态&#xff0…

运放失调电压及其影响

运放失调电压及其影响 在运放的应用中&#xff0c;我们经常会遇到一个重要的性能指标——失调电压。本文将介绍失调电压的定义、优劣范围&#xff0c;并提供一些应对失调电压的方法。 定义 在运放开环使用时&#xff0c;加载在两个输入端之间的直流电压使得放大器直流输出电…

基于斑翠鸟优化算法(Pied Kingfisher Optimizer ,PKO)的无人机三维路径规划(MATLAB)

一、无人机路径规划模型介绍 二、算法介绍 斑翠鸟优化算法(Pied Kingfisher Optimizer ,PKO),是由Abdelazim Hussien于2024年提出的一种基于群体的新型元启发式算法,它从自然界中观察到的斑翠鸟独特的狩猎行为和共生关系中汲取灵感。PKO 算法围绕三个不同的阶段构建:栖息…

利用Java实现数据矩阵的可视化

1. 引言 在进行工程开发时&#xff0c;通常需要在窗口的某个区域将有效数据形象化地呈现出来&#xff0c;例如&#xff1a;对于某一区域的高程数据以伪色彩的方式呈现出高度的变化&#xff0c;这就需要解决利用Java进行数据呈现的问题。本文将建立新工程开始&#xff0c;逐步地…

VScode(Python)使用ssh远程开发(Linux系统树莓派)时,配置falke8和yapf总结避坑!最详细,一步到位!

写在前面&#xff1a;在Windows系统下使用VScode时可以很舒服的使用flake8和yapf&#xff0c;但是在ssh远程开发树莓派时&#xff0c;我却用不了&#xff0c;总是出现问题。当时我就开始了漫长的探索求知之路。中间也请教过许多大佬&#xff0c;但是他们就讲“能用不就行了&…

LabVIEW电磁阀特性测控系统

LabVIEW电磁阀特性测控系统 电磁阀作为自动化工程中的重要组成部分&#xff0c;其性能直接影响系统的稳定性和可靠性。设计一种基于LabVIEW的电磁阀特性测控系统&#xff0c;通过高精度数据采集和智能化控制技术&#xff0c;实现电磁阀流阻、响应时间及脉冲特性的准确测量和分…

【MySQL性能优化】- 一文了解MVCC机制

MySQL理解MVCC &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xff0c;欢迎指正&#xff…

docker部署springboot jar包项目

docker部署springboot jar包项目 前提&#xff0c;服务器环境是docker环境&#xff0c;如果服务器没有安装docker&#xff0c;可以先安装docker环境。 各个环境安装docker&#xff1a; Ubuntu上安装Docker&#xff1a; ubuntu离线安装docker: CentOS7离线安装Docker&#xff1…

应急响应实战笔记03权限维持篇(6)

0x00 前言 在渗透测试中&#xff0c;有三个非常经典的渗透测试框架----Metasploit、Empire、Cobalt Strike。 那么&#xff0c;通过漏洞获取到目标主机权限后&#xff0c;如何利用框架获得持久性权限呢&#xff1f; 0x01 MSF权限维持 使用MSF维持权限的前提是先获得一个met…

开关电源的线性调整率是什么?怎么检测线性调整率?

开关电源线性调整率 开关电源线性调整率是指输入电压在额定范围内变化时&#xff0c;开关电源输出电压随之变化的比率。线性调整率对开关电源的电压稳定性有着重要影响&#xff0c;通常开关电源的线性调整率在1%~5%之间。线性调整率越小&#xff0c;说明电压越稳定&#xff1b;…

Maven编译:Failed to execute goal……Fatal error compiling

问题描述 mvn编译报错 Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.10.1:compile (default-compile) on project postion-report-service: Fatal error compiling 解决方法 pom.xml 中java.version配置为11 检查Maven中的jre是否配置正确

1.下载安装ESP32开发环境ESP-IDE

ESP32简介 ESP32介绍 说到ESP32&#xff0c;首先ESP32不是一个芯片&#xff0c;ESP32是一个系列芯片&#xff0c; 是乐鑫自主研发的一系列芯片微控制器。它主要的功能就是支持WiFi和蓝牙&#xff0c; ESP32指的是ESP32裸芯片。但是&#xff0c;“ESP32”一词通常指ESP32系列芯…

11.用AI运行AI

文章目录 Godmode使用示例概念Recursive Reprompting and Revision(Re3)Language Models as Zero-Shot PlannersHuggingGPTLanguage models can solve computer tasks 部分截图来自原课程视频《2023李宏毅最新生成式AI教程》&#xff0c;B站自行搜索。 用AI运行AI&#xff0c;顾…

PBKDF2算法:保障密码安全的利器

title: PBKDF2算法&#xff1a;保障密码安全的利器 date: 2024/3/14 16:40:05 updated: 2024/3/14 16:40:05 tags: PBKDF2算法密码安全性迭代盐值密钥 PBKDF2算法起源&#xff1a; PBKDF2&#xff08;Password-Based Key Derivation Function 2&#xff09;算法是一种基于密码…

【计算机网络实践】FileZilla Server1.8.1实现局域网ftp文件传输

大二新生随便写写笔记&#xff0c;轻喷&#xff0c;鉴于本人在网络搜索中并未搜索到1.8.1版本的使用方法&#xff0c;因而瞎写一页。 一、准备 下载一个FileZilla Server1.8.1在你想作为服务器的主机上&#xff08;此处直接在官网下载即可&#xff1a;Download FileZilla Serve…