分巧克力 刷题笔记

/*
分巧克力 解题思路
二分
直接检查看答案是否符合题目条件
对于一块边长分别为x 和y的巧克力\\
假设我们输入检查的数为k
其能分割成的 k*k 的巧克力的块数为
(x/k)*(y/k)
因为c++里面的除法是下取整的所以我们不用考虑奇偶数 是否能整除
将每一块巧克力能分成的k*k的巧克力块数加上计数器
一旦计数器超过了孩子数 我们就返回true;
如果check 不通过的话 可能是分的太大了
所以答案小于mid
于是我们让r=mid-1
如果check通过
则答案>=mid 所以我们让l=mid
重点 讨论边界情况
例如案例中
2 10
6 5
5 6
输出2
当 l指向2 r指向3
mid=(l+r)>>1;的话 mid 是2
此时check可以通过
但是l=2,r=3;
如果还是l=mid=2则陷入死循环
于是 我们让mid=(l+r+1)>>1
让其进行上取整
则 mid=3;
check不通过
此时 r=mid-1=l;
退出循环
输出l或者r即可
*/
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
struct node{
int x;
int y;
}a[N];
int n,k;
bool check(int p){
int cnt=0;
bool flag=false;
// cout<<"p is "<<p<<endl;
for(int i=0;i<n;i++){
cnt=cnt+(a[i].x /p)*(a[i].y /p);
//cout <<cnt<<endl;
if(cnt>=k){
flag= true;
break;
}
}
return flag;
}
int main(){
cin>>n>>k;
int r=0;
for(int i=0;i<n;i++){
cin>>a[i].x >>a[i].y;
if(a[i].x >a[i].y ){
if(a[i].x >r){
r=a[i].x ;
}
}else{
if(a[i].y >r){
r=a[i].y ;
}
}
}
// cout<<r<<endl;
int l=0;
while(l<r){
int mid=(l+r+1)>>1;
//cout<<mid<<endl;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
//cout<<"l is"<<l<<endl<<"r is "<<r<<endl;
}
cout <<l;
return 0;
}
相关文章:
分巧克力 刷题笔记
/* 分巧克力 解题思路 二分 直接检查看答案是否符合题目条件 对于一块边长分别为x 和y的巧克力\\ 假设我们输入检查的数为k 其能分割成的 k*k 的巧克力的块数为 (x/k)*(y/k) 因为c里面的除法是下取整的所以我们不用考虑奇偶数 是否能整除 将每一块巧克力能分成的k*k的巧克力…...
Python图像处理【21】基于卷积神经网络增强微光图像
基于卷积神经网络增强微光图像 0. 前言1. MBLLEN 网络架构2. 增强微光图像小结系列链接 0. 前言 在本节中,我们将学习如何基于预训练的深度学习模型执行微光/夜间图像增强。由于难以同时处理包括亮度、对比度、伪影和噪声在内的所有因素,因此微光图像增…...
【嵌入式——QT】QTreeWidget
QTreeWidget类是创建和管理目录树结构的类,QTreeWidget每一个节点都是一个QTreeWidgetItem对象,添加一个节点前需先创建。QTreeWidget类是一个便利类,它提供了一个标准的树widget,具有经典的基于item的界面,类似于Qt 3…...
SQL 术语:Join 中的 Build 和 Probe 是什么意思?
博主历时三年精心创作的《大数据平台架构与原型实现:数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行,点击《重磅推荐:建大数据平台太难了!给我发个工程原型吧!》了解图书详情,…...
HTTP头部信息解释分析(详细整理)
这篇文章为大家介绍了HTTP头部信息,中英文对比分析,还是比较全面的,若大家在使用过程中遇到不了解的,可以适当参考下 HTTP 头部解释 1. Accept:告诉WEB服务器自己接受什么介质类型,*/* 表示任何类型&#…...
探究短链接生成算法
1. 引言 在互联网时代,链接是连接用户和信息的桥梁,而长链接可能会因为过长、难记、不美观等问题影响用户体验,因此短链接的出现填补了这一空缺。短链接是将原始的长链接通过一定的算法转换成短字符串,从而实现了链接的简洁化&am…...
golang 实现http请求的调用,访问并读取页面数据和内置的一些方法
下午就不能好好学习一下golang,业务一直找个不停,自己定的业务规则都能忘得一干二净,让你查半天,完全是浪费时间。 golang实现访问并读取页面数据 package mainimport ("fmt""net/http" )var urls []string{…...
FFmpeg+OpenCV开发案例汇总
桌面共享工具(软编版) 桌面共享工具(DXGI硬编版) 智能广告大屏(可叠加透明广告) Android手机屏幕RTMP推流工具(推麦克风版) Android手机屏幕RTMP推流工具(推扬声器版…...
PySide6+VSCode Python可视化环境搭建
pip install pyside6 下载本期源码 vscode装一个PYQT Integration插件,设置好两个路径(下面有个脚本用于获取路径) 用everything的童鞋注意了:工具/选项/索引/强制重建 重启vscode可以看到,右击.ui文件时出现可以操作…...
【设计】设计一个web版的数据库管理平台后端精要
需求 springboot设计开发一个系统,在这个系统的数据库表中存放着2000个数据库实例,有MySQL、Oracle、sql server3种数据库类型,用户可以在页面上选择不同的实例,连接这些实例上的数据库,来执行业务sql 实现 Service…...
没有硬件基础可以学单片机吗?
没有硬件基础可以学单片机吗? 在开始前我分享下我的经历,我刚入行时遇到一个好公司和师父,给了我机会,一年时间从3k薪资涨到18k的, 我师父给了一些 电气工程师学习方法和资料,让我不断提升自己,…...
ChatGPT引领的AI面试攻略系列:cuda和tensorRT
系列文章目录 cuda和tensorRT(本文)AI全栈工程师 文章目录 系列文章目录一、前言二、面试题1. CUDA编程基础2. CUDA编程进阶3. 性能优化4. TensorRT基础5. TensorRT进阶6. 实际应用与案例分析7. 编程与代码实践8. 高级话题与趋势 一、前言 随着人工智能…...
【战略前沿】人形机器人制造商Figure获得了OpenAI、Jeff Bezos、Nvidia和其他科技巨头的资助
原文:Humanoid robot-maker Figure gets funding from OpenAI, Jeff Bezos, Nvidia, and other tech giants 作者:ASSOCIATED PRESS ———————————————— Figure成立不到两年,还没有商业产品,但正在说服有影响力的…...
多块磁盘组磁盘离线导致VSAN存储崩溃的VSAN数据恢复案例
VSAN简介: VSAN是以vSphere内核为基础进行开发、可扩展的分布式存储架构。VSAN存储层由VSAN控制和管理,VSAN存储层是通过vSphere集群主机中闪存和硬盘的存储空间构建的,供vSphere集群使用的统一共享存储层。 VSAN存储是一个对象存储ÿ…...
Jenkins 的安装(详细教程)
文章目录 一、简介二、安装前准备三、windows 安装与启动1. 方式一2. 方式二3. 方式三 四、创建管理员用户五、常用设置1. 配置镜像地址2. 更改工作目录3. 开启可注册用户4. 全局变量配置 一、简介 官网:https://www.jenkins.io 中文文档:https://www.j…...
使用html网页播放多个视频的几种方法
前言 因为项目测试需要,我需要可以快速知道自己推流的多路视频流质量,于是我想到可以使用html网页来播放视频,实现效果极其简单,方法有好几种,以下是几种记录: 注意:测试过,VLC需要使…...
python 基础知识点(蓝桥杯python科目个人复习计划58)
今日复习内容:做题 例题1:仙境诅咒 问题描述: 在一片神秘的仙境中,有N位修仙者,他们各自在仙境中独立修炼,拥有他们独特的修炼之地和修炼之道,修炼者们彼此之间相互尊重,和平相处…...
【基于React实现共享单车管理系统】—React基础知识巩固(二)
【基于React实现共享单车管理系统】—React基础知识巩固(二) 一、React介绍 Facebook开源的一个JavaScript库React结合生态构成的一个MV*库 React的特点 Declarative(声明式编码)Component-Based(组件化编码&#…...
云桥通+跨境电商:SDWAN企业组网优化跨境网络案例
跨境电商企业在全球范围内展开业务,需构建稳定高效的网络架构以支持其电商平台运营。云桥通SDWAN企业组网技术为跨境电商提供网络连接和管理的优化,提升网络性能、可靠性和安全性。以下是一家跨境电商企业的SDWAN组网案例,详细介绍其实施情况…...
服务器有几种http强制跳转https设置方法
目前为站点安装SSL证书开启https加密访问已经是件很简单的事了,主要是免费SSL证书的普及,为大家提供了很好的基础。 Apache环境下如何http强制跳转https访问。Nginx环境下一般是通过修改“你的域名.conf”文件来实现的。 而Apache环境下通过修改.htacces…...
Fish Speech 1.5镜像免配置指南:3步启动WebUI生成高自然度语音
Fish Speech 1.5镜像免配置指南:3步启动WebUI生成高自然度语音 想给视频配音,但找不到合适的声音?想制作有声书,又觉得录音太麻烦?或者,你只是想体验一下用AI生成一段媲美真人的语音? 今天&am…...
终极指南:3步解锁原神帧率限制,体验144Hz流畅游戏
终极指南:3步解锁原神帧率限制,体验144Hz流畅游戏 【免费下载链接】genshin-fps-unlock unlocks the 60 fps cap 项目地址: https://gitcode.com/gh_mirrors/ge/genshin-fps-unlock genshin-fps-unlock是一款专为《原神》PC玩家设计的帧率解锁工具…...
BililiveRecorder工具箱深度解析:专业级FLV直播录制文件修复解决方案
BililiveRecorder工具箱深度解析:专业级FLV直播录制文件修复解决方案 【免费下载链接】BililiveRecorder 录播姬 | mikufans 生放送录制 项目地址: https://gitcode.com/gh_mirrors/bi/BililiveRecorder BililiveRecorder工具箱提供了一套完整的直播录制文件…...
QCS6490实战解码:从参数到场景的性能跃迁指南
1. QCS6490硬件性能的实战价值解码 第一次拿到QCS6490开发板时,我对着参数表发呆了半小时——12TOPS算力、5路ISP、Wi-Fi 6E这些参数看起来很厉害,但到底能解决哪些实际问题?经过三个月的项目实战,我发现这款芯片的真正价值在于将…...
如何用3步永久保存QQ空间回忆?GetQzonehistory全攻略
如何用3步永久保存QQ空间回忆?GetQzonehistory全攻略 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 你是否担心过QQ空间里那些承载青春记忆的说说会突然消失?Ge…...
在PHP中,何时使用静态工厂方法替代构造函数?
在 PHP 中,构造函数 (__construct) 是实例化对象的默认方式,但它有几个明显的局限性: 名称固定:只能叫 __construct,无法表达意图。返回类型固定:只能返回当前类的实例,不能返回子类或缓存对象。…...
从底层源码深入分析Bean的实例化
在技术领域,我们常常被那些闪耀的、可见的成果所吸引。今天,这个焦点无疑是大语言模型技术。它们的流畅对话、惊人的创造力,让我们得以一窥未来的轮廓。然而,作为在企业一线构建、部署和维护复杂系统的实践者,我们深知…...
PICO开发效率翻倍:手把手教你用PDC串流实现Unity场景‘所见即所得’
PICO开发效率革命:用PDC串流实现Unity场景实时同步的终极指南 在VR内容开发领域,迭代效率往往决定着项目的成败。传统开发流程中,开发者需要反复在Unity编辑器和头显设备之间切换,每次修改后都要经历漫长的构建部署过程࿰…...
霜儿-汉服-造相Z-Turbo应用指南:打造你的江南庭院古风AI摄影师
霜儿-汉服-造相Z-Turbo应用指南:打造你的江南庭院古风AI摄影师 1. 模型介绍与核心功能 1.1 什么是霜儿-汉服-造相Z-Turbo 霜儿-汉服-造相Z-Turbo是一款专注于生成古风汉服人像的AI文生图模型。它基于强大的Z-Image-Turbo基础模型,通过LoRA(…...
DAMOYOLO-S数据库联动应用:检测结果自动化存储与查询
DAMOYOLO-S数据库联动应用:检测结果自动化存储与查询 你有没有遇到过这样的场景?一个智能安防摄像头,每天24小时不间断地运行,DAMOYOLO-S模型在里面兢兢业业地识别着每一个经过的人和车。但问题是,这些宝贵的检测结果…...
