P1824 进击的奶牛题解

题目

Farmer John 建造了一个有N(2≤N≤105) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是x_{1},x_{2},\cdots ,x_{N}(0≤x_{i}​≤10^{9})。

他的C(2≤C≤N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?

输入输出格式

输入格式

第1行:两个用空格隔开的数字N和C。

第2∼N+1行:每行一个整数,表示每个隔间的坐标。

输出格式

输出只有一行,即相邻两头牛最大的最近距离。

输入输出样例

输入样例

5 3
1
2
8
4
9

输出样例

3

解析

这道题目还是按照套路构造条件,可以把c头牛全部安置进这些隔间使相邻两头牛距离不超过x。于是先得检验单调性:可以看出,x越小,就越可能把所有牛合法安置;当x比较大时,牛棚就不够安置了。于是不难想象,存在一个分界线ans,x大于ans时没有合法安置方案,x小于等于ans时,则一定存在合法安置方案。

此题目只有一个限制,即任意两个相邻安置点距离不能小于x。于是可以采用感受到一种贪心算法:从最左端开始,每隔超过x的距离,能安置就安置,最后只要看遍历所有点以后总共安置了多少头牛即可。

#include<iostream>
#include<algorithm>
#define maxn 1000010
#define inf 1e9
using namespace std;
int a[maxn],n,c;
bool p(int d){
	int k=0,last=-inf;//last记录上一头牛的安置坐标 
	for(int i=1;i<=n;i++){
		if(a[i]-last>=d){//能安置就立刻安置 
			last=a[i];
			k++;
		}
	}
	return k>=c;
}
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int l=0,r=inf,ans,mid;
	while(l<=r){
		if(p(mid=l+r>>1)){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}

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

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

相关文章

“比特币突破5.2万美元”,一枚币可换一斤半黄金?黄金比特币之争再次甚嚣尘上!

自今年1月美国SEC批准比特币现货ETF登陆美股市场之后&#xff0c;只用了短短的30个交易日&#xff0c;比特币ETF就从零膨胀到了近400亿美元的规模&#xff0c;超过白银ETF约100多亿美元的规模&#xff0c;和规模约为900多亿美元的黄金ETF暂时形成了“三七开”的格局。比特币现货…

毕业设计:基于知识图谱的《红楼梦》人物关系可视化

文章目录 项目介绍部署步骤项目运行 项目介绍 github地址&#xff1a;https://github.com/chizhu/KGQA_HLM?tabreadme-ov-file 基于知识图谱的《红楼梦》人物关系可视化&#xff1a;应该是重庆邮电大学林智敏同学的毕业设计&#xff0c;在学习知识图谱的过程中参考使用。 文…

ESP8266 烧录 MQTT固件

~~ 文章约定 ~~ 约定1&#xff1a;本篇所述固件&#xff0c;已测试可用于阿里云连接&#xff0c;其它云&#xff0c;未测试。 约定2&#xff1a;本烧录方法&#xff0c;以魔女开发板的板载ESP8266作示范。 约定3&#xff1a;如果使用独立的CH340、独立的ESP8266&#xff0c;请…

Puresuit 轨迹跟踪

在网上看过了很多Puresuit的轨迹跟踪算法&#xff0c;看起来都写的差不多&#xff0c;用起来不会用。 套用一份demo,在C转C语言的时候又深入理解了一些&#xff0c;在此整理成文档&#xff0c;供大家参考。输入 1.输入量是什么; 要知道车的长度&#xff0c;车的后轮位置以及下…

Redis(03)——发布订阅

基础命令 基于频道 publish channel message&#xff1a;将信号发送到指定的频道pubsub subcommand [argument [argyment]]&#xff1a;查看订阅或发布系统状态subscribe channel [channel]&#xff1a;订阅一个或多个频道的信息unsubscribe [channel [channel]]&#xff1a;退…

Leetcode 1089.复写零

目录 题目 思路 代码 题目 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改&#xff0c;不要从函数返回…

javascript选择器大全

目录 1.getElementsByTagName 2.getElementsByName 3.getElementById 4.getElementsByClassName 5.querySelector 6.querySelectorAll 1.getElementsByTagName 俗称标签选择器&#xff0c;可以根据标签名查找匹配到页面的元素对象&#xff0c;返回为一个数组。 <div&…

google邮箱开启两步验证

我开发的chatgpt网站&#xff1a; https://chat.xutongbao.top/

美国Mercari煤炉注册教程,还不快来Get!

想要掘金全球电商市场&#xff0c;美国的Mercari平台绝对值得关注。Mercari&#xff0c;也被称作煤炉&#xff0c;类似于我们国内的闲鱼二手交易平台&#xff0c;它同时拥有美国和日本两个市场。其中&#xff0c;美国市场的消费需求稳定且持续增长&#xff0c;成为了许多跨境电…

Gradle8之下载安装与环境变量配置及国内下资源设置

Gradle8之下载安装与环境变量配置及国内下资源设置 文章目录 Gradle8之下载安装与环境变量配置及国内下资源设置1. Gradle1. 官网2. 关于Gradle1. 构建任何内容2. 自动化一切3. 更快地交付 2. 下载与安装1. 下载2. 环境变量3.本地存储路径4. 查看Gradle版本 3. 配置国内下资源1…

GZ036 区块链技术应用赛项赛题第8套

2023年全国职业院校技能大赛 高职组 “区块链技术应用” 赛项赛卷&#xff08;8卷&#xff09; 任 务 书 参赛队编号&#xff1a; 背景描述 现实中患者私密信息泄露情况时有发生&#xff0c;医疗部门的柜式存储和纸质记录已不再是最优选择。在2015-2016年间&…

爬虫知识--01

爬虫介绍 # 爬虫的概念&#xff1a; 通过编程技术(python:request,selenium)&#xff0c;获取互联网中的数据(app&#xff0c;小程序&#xff0c;网站)&#xff0c;数据清洗(xpaht&#xff0c;lxml)后存到库中(mysql&#xff0c;redis&#xff0c;文件&#xff0c;excel&#x…

探索未来-Sora

AI如何将静态图像转化为动态、逼真的视频&#xff1f; OpenAI 的 Sora 通过时空片段&#xff08;以下统称片段&#xff09;的创新使用给出了答案。 Sora 展示与探讨 在快速发展的生成模型领域&#xff0c;OpenAI 的 Sora成为一个重要的里程碑&#xff0c;有望重塑我们对视频生…

uniapp离线打包(使用Android studio打包)

一、准备工作 安装HbuilderX&#xff0c;记住版本号下载对应HbuilderX版本的Android离线SDK&#xff0c;如我使用3.6.18版本打包&#xff0c;则对应应下载3.6.18版本的SDK&#xff08;官网不提供旧版本的SDK&#xff0c;有些需要自己找&#xff09;官网下载地址&#xff1a;ht…

亚马逊鲲鹏系统一键注册亚马逊买家号的软件

在如今的电商世界中&#xff0c;自动注册亚马逊买家号已经成为了一种必要的操作需求。为了规避关联性问题&#xff0c;许多用户选择借助专门设计的软件工具&#xff0c;其中最为流行的就是亚马逊鲲鹏系统。这款软件以其自带防指纹浏览器和全自动化操作功能而闻名。 亚马逊鲲鹏系…

《摔跤吧爸爸》19岁女星突患皮肌炎离世

从确诊到离世仅10天……罕见病“皮肌炎”&#xff01; 曾凭借在知名电影《摔跤吧&#xff01;爸爸》中饰演童年时期“小芭比塔”一角而广受喜爱的年轻演员苏哈尼巴特纳格尔不幸离世&#xff0c;年仅19岁。她的突然逝世引发了全球关注&#xff0c;据苏哈妮的家人表示&#xff0…

基于docker安装HDFS

1.docker一键安装见 docker一键安装 2.拉取镜像 sudo docker pull kiwenlau/hadoop:1.03.下载启动脚本 git clone https://github.com/kiwenlau/hadoop-cluster-docker4.创建网桥 由于 Hadoop 的 master 节点需要与 slave 节点通信&#xff0c;需要在各个主机节点配置节点…

ACE 中的Active Object模式

Active Object 设计模式&#xff1a; 1&#xff09; 根据对象被调用的方式&#xff0c;可以将对象分为两类: Passive Object和Active Object。Passive 和 Object和调用者在同一个线程中&#xff0c;这就是我们通常所用的函数调用。而Active Object和调用在不同的线程中&#xf…

漏洞挖掘 | 编辑器漏洞之kindeditor

本文由掌控安全学院 - master666 投稿 今天呢给大家复现一个kindeditor<4.1.5上传漏洞。小弟能力有限&#xff0c;还在坚持学习的路上&#xff0c;还请大佬多多指教。自我感觉编辑器漏洞很容易忽视。此文章作为记录本人学习的开始&#xff0c;丰富自己的阅历。我们共同进步…

TLS指纹校验原理和绕过

TLS指纹校验原理和绕过 1.指纹校验案例 当用浏览器访问时能够正常访问&#xff0c;而用代码请求却得不到相应结果 1.1 案例&#xff1a;ascii2d https://ascii2d.net/ 1.2 案例&#xff1a;investing https://cn.investing.com/equities/amazon-com-inc-historical-data 2.T…