进击的奶牛
题目
进击的奶牛
题意
- 通过二分查找算法找到一个最小间距x,使得在数组a中选出的k个数两两之间的间距都不小于x,并且x尽可能大。最后输出这个最大的x值。
思路
- 程序通过循环依次获取了n个整数,存储在数组a中。
- .然后,程序对数组a进行了排序,以便进行二分查找。
- 接着,程序使用二分查找算法来寻找满足条件的最小间距。在二分查找的过程中,通过调用check函数来判断当前的间距m是否满足条件。
- 在check函数中,程序遍历数组a,计算相邻元素之间的间距,并统计满足条件的间距数量。
- 最后,程序输出满足条件的最小间距ans。
坑点
- l和r边界问题
算法一:二分
实现步骤
- 程序通过循环依次获取了n个整数,存储在数组a中。
- .然后,程序对数组a进行了排序,以便进行二分查找。
- 接着,程序使用二分查找算法来寻找满足条件的最小间距。在二分查找的过程中,通过调用check函数来判断当前的间距m是否满足条件。
- 在check函数中,程序遍历数组a,计算相邻元素之间的间距,并统计满足条件的间距数量。
- 最后,程序输出满足条件的最小间距ans。
代码
#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010],ans;
bool check(int x)
{int d=a[1],sum=1;for(int i=2;i<=n;i++){if(a[i]-d>=x){sum++;d=a[i];} }return sum>=k;
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}int l=1,r=1e9;sort(a+1,a+n+1);while(l<=r){int m=l+r>>1;if(check(m)){ans=m;l=m+1;}else{r=m-1;}}cout<<ans;return 0;
}
相关文章:
进击的奶牛
题目 进击的奶牛 题意 通过二分查找算法找到一个最小间距x,使得在数组a中选出的k个数两两之间的间距都不小于x,并且x尽可能大。最后输出这个最大的x值。 思路 程序通过循环依次获取了n个整数,存储在数组a中。.然后,程序对数组a进…...
12月27日,每日信息差
以下是2023年12月27日的8条信息差 第一、小米公司:小米汽车正式加入小米“人车家全生态”,随着小米汽车的即将发布,小米“人车家全生态”也实现了真正闭环 第二、吉利将于2024年初发射11颗卫星,吉利银河E8率先搭载卫星通信技术。…...

【赠书第14期】AI短视频制作一本通:文本生成视频+图片生成视频+视频生成视频
文章目录 前言 1 前期准备 2 拍摄与录制 3 后期编辑 4 技巧与注意事项 5 推荐图书 6 粉丝福利 前言 随着智能技术的迅猛发展,AI 短视频制作成为了一种新兴而创新的表达方式,广泛应用于社交媒体、广告营销、教育培训等领域。本文将介绍 AI 短视频…...
简单工厂设计模式(计算器实例优化)
简单工厂设计模式(计算器实例优化) 介绍为什么采用面向对象编程而不是面向过程呢?实例讲解业务层划分出来逻辑层继承简单工厂:(多态)业务层:(解耦合)主控制台 总结 介绍 …...

iconify图标集离线使用方案简介
1.需求描述 前端项目,技术栈使用Vue3Element Plus,参考了ruoyi-vue-pro项目与vue-element-plus-admin项目,封装了一个Icon组件,图标使用的是iconify,项目部署在内网环境,不能连接互联网,需要部署一套iconi…...
java基础之理解多态
目录 简单理解 满足多态的三个条件 有类继承或者接口实现 子类要重写父类的方法 父类的引用指向子类的对象。 代码示例 动态多态 静态多态 个人观点 简单理解 简单理解就是,同一操作作用于不同的对象,可以有不同的解释,产生不同的执…...

第二证券:A股市场放量反弹 跨年行情或启动
沪指日线等级放量反弹,周四收中阳线成功站上20日均线,底部结构或可树立。创业板指大涨近4%,日线MACD出现底违反,多方动能较强,中等级反弹行情或在酝酿。月线来看,12月创业板指探底上升出现较长下影…...

web漏洞与修复
一、web漏洞 检测到目标X-Content-Type-Options响应头缺失 详细描述X-Content-Type-Options HTTP 消息头相当于一个提示标志,被服务器用来提示客户端一定要遵循在 Content-Type 首部中对 MIME 类型 的设定,而不能对其进行修改。这就禁用了客户端的 MIM…...

基于Java+SpringBoot+vue实现图书借阅管理系统
基于JavaSpringBootvue实现图书借阅和销售商城一体化系统 🍅 作者主页 程序设计 🍅 欢迎点赞 👍 收藏 ⭐留言 📝 🍅 文末获取源码联系方式 📝 文章目录 基于JavaSpringBootvue实现图书借阅和销售商城一体化…...
xml文件学习(xml格式)可扩展标记语言(Extensible Markup Language)
XML 教程 文章目录 XML 文件学习1. XML 概述1.1 什么是 XML?1.2 XML 有什么作用? 2. XML 基本结构1. 声明2. 元素3. 属性4. 文本5. 注释 3. XML 高级知识3.1 XML 命名空间3.2 XML 架构3.3 XML 工具3.4 XML 技术 4. XML 应用实例 XML 文件学习 XML&#…...

nodejs+vue+ElementUi家政服务系统c90g5
项目中登录模块用到token家政服务平台有管理员,雇主,雇员三个角色。管理员功能有个人中心,雇主管理,雇员管理,资料认证管理,项目类型管理,服务项目管理,需求信息管理,服务…...

数据库(Database)基础知识
什么是数据库 数据库是按照数据结构来组织、存储和管理数据的仓库,用户可以通过数据库管理系统对存储的数据进行增删改查操作。 数据库实际上是一个文件集合,本质就是一个文件系统,以文件的方式,将数据保存在电脑上。 什么是数据…...

QT应用篇 二、QML用Image组件实现Progress Bar 的效果
QT应用篇 一、QT上位机串口编程 二、QML用Image组件实现Progress Bar 的效果 三、QML自定义显示SpinBox的加减按键图片及显示值效果 文章目录 QT应用篇前言一、qml需求二、使用组件1.Image组件2.Image中fillMode的使用例子 总结 前言 记录自己学习QML的一些小技巧方便日后查找…...
SElinux工作原理简介并演示chcon、semanage、restorecon的使用方法
目录 一.SElinux工作原理简介 1.system_u 2.object_r 3.httpd_sys_content_t 4.s0 二.SElinux策略的具体使用详情 1.restorecon 2.semanage 3.chcon 一.SElinux工作原理简介 通过mac方式管理进程,管理的目标是进程是否具有读取权限的文件(文件…...
表情串转换
前言 NWAFU 2021阶段二 D 一、题目描述 题目描述 在一个字符串中,设置了由‘/’前导字符和某些特定字母构成的转义子字符串,如“/s”、“/f”、“/c”等用于表示特殊表情符号。现要求编写一个函数,将给定字符串中的转义字符串转换为表情字…...

【娱乐小技巧】网页旋转90° 3步搞定
一、按F12,打开控制台; 二、点击号; 插入新body; 三、粘贴代码 -webkit-transform: rotate(90deg);小结,角度值可以自选; 代码的效果:...

移动管理系统软件哪家好?它是如何帮助企业降本增效的?
现在很多管理系统都可以用移动设备接入,最常见的就是手机。只要给管理系统创建一个微信小程序接口,那么要使用系统功能的时候直接打开微信小程序就可以了。例如我们小区的物业巡检就是通过微信扫码打开巡检工单记录信息的,直接用巡检保安自己…...

电脑表格文件丢失如何找回?3个方法拯救丢失的文件!
“太难了!我辛辛苦苦在电脑上做的表格,不知道什么原因突然就没有了,有什么方法可以找回丢失的表格文件吗?快帮帮我吧!” 在日常工作中,很多电脑用户可能都会用到表格文件,这往往记载了大量的重要…...

VSCode 如何安装插件的历史版本
背景 在日常开发过程中,我们可能会遇到新版VSCode插件存在问题,无法正常工作的情况。这种情况下,一种可行的解决方案就是安装插件的历史版本。VSCode 插件默认安装的都是插件最新的版本,例如下面 vscode-styled-compoents 插件 本…...
关于edge浏览器以及插件推荐
目录 广告拦截和隐私工具 密码管理器 生产力和组织工具 写作和语法工具 购物助手 娱乐和个性化 安全性和VPN 开发者工具 其他实用工具 Microsoft Edge 是一款基于Chromium开源项目的现代网络浏览器,由微软开发。它是Internet Explorer的继任者,…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...