当前位置: 首页 > news >正文

【C++ 真题】P1824 进击的奶牛

P1824 进击的奶牛

题目描述

Farmer John 建造了一个有 N N N 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2N105) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1,x2,,xN 0 ≤ x i ≤ 1 0 9 0 \leq x _ i \leq 10 ^ 9 0xi109)。

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5 3
1
2
8
4
9

输出 #1

3

题解

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6+7;
int n, C, x, b;
int g[N], sum = 1, ans, mid;
int main() {cin>>n>>C;for(int i=1;i<=n;++i){cin>>g[i];}sort(g+1, g+n+1);int l = g[1], r = g[n];while(l<r){sum = 1;mid = l+(r-l)/2; int cow = g[1];for(int j=2;j<=n;++j){if(g[j] - cow >= mid){sum++;cow = g[j];}}if(sum>=C) {ans = mid;l = mid + 1;}else{r = mid;}}cout<<ans<<endl;return 0;
}

相关文章:

【C++ 真题】P1824 进击的奶牛

P1824 进击的奶牛 题目描述 Farmer John 建造了一个有 N N N&#xff08; 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2≤N≤105) 个隔间的牛棚&#xff0c;这些隔间分布在一条直线上&#xff0c;坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1​,x2​,⋯,xN​&a…...

26、深度学习-自学之路-NLP自然语言处理-理解加程序,怎么把现实的词翻译给机器识别。

一、怎么能让机器能够理解我们的语言呢&#xff0c;我们可以利用神经网络干很多的事情&#xff0c;那么我们是不是也可以用神经元做自然语言处理呢&#xff0c;现在很多的实际应用已经说明了这个问题&#xff0c;可以这么做。 那我们考虑一下该怎么做&#xff0c;首先我们应该…...

24电子信息类研究生复试面试问题汇总 电子信息类专业知识问题最全!电子信息复试全流程攻略 电子信息考研复试真题汇总

你是不是在为电子信息考研复试焦虑&#xff1f;害怕被老师问到刁钻问题、担心专业面答不上来&#xff1f;别慌&#xff01;作为复试面试92分逆袭上岸的学姐&#xff0c;今天手把手教你拆解电子信息类复试通关密码&#xff01;看完这篇&#xff0c;让你面试现场直接开大&#xf…...

leetcode25. K 个一组翻转链表

代码如图所示&#xff1a;下面还有一个跑代码的流程图&#xff0c;结合两个图片理解起来就好&#xff0c;感觉已经解释的很清晰了&#xff01;&#xff01; 一定要记住return dummy.next;这表示伪节点的下一个节点才是反转完的整个链表的头结点 补一个最后的&#xff0c;有点纰…...

工厂方法模式详解(Java)

一、工厂方法模式基础 1.1 定义与角色 工厂方法模式(Factory Method Pattern)是一种创建型设计模式,它提供了一种创建对象的接口,但允许子类决定实例化哪一个类。这种模式的核心在于定义一个创建产品对象的工厂接口,将实际创建产品的过程延迟到子类中实现。这样做的主要…...

SpringBoot+Dubbo+zookeeper 急速入门案例

项目目录结构&#xff1a; 第一步&#xff1a;创建一个SpringBoot项目&#xff0c;这里选择Maven项目或者Spring Initializer都可以&#xff0c;这里创建了一个Maven项目&#xff08;SpringBoot-Dubbo&#xff09;&#xff0c;pom.xml文件如下&#xff1a; <?xml versio…...

pdf.js默认显示侧边栏和默认手形工具

文章目录 默认显示侧边栏(切换侧栏)默认手形工具(手型工具) 大部分的都是在viewer.mjs中的const defaultOptions 变量设置默认值,可以使用数字也可以使用他们对应的变量枚举值 默认显示侧边栏(切换侧栏) 在viewer.mjs中找到defaultOptions,大概在732行,或则搜索sidebarViewOn…...

数据库第三次作业

第一题&#xff1a; 学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;S…...

渗透利器:YAKIT 工具-基础实战教程.

YAKIT 工具-基础实战教程. YAKIT&#xff08;Yak Integrated Toolkit&#xff09;是一款基于Yak语言开发的集成化网络安全单兵工具&#xff0c;旨在覆盖渗透测试全流程&#xff0c;提供从信息收集、漏洞扫描到攻击实施的自动化支持。其核心目标是通过GUI界面降低Yak语言的使用…...

变分边界详解

起因 当时看VAE论文时有这么一段&#xff0c;但是看完直接一头雾水&#xff0c;这都那跟哪&#xff0c;第一个公式咋做的变换就变出那么一堆。网上搜了很多博客都语焉不详&#xff0c;只好自己来写一篇&#xff0c;希望能解答后来人的疑惑。 公式1 参考文章&#xff1a;证据…...

计算机毕业设计——Springboot餐厅点餐系统

&#x1f389;**欢迎来到琛哥的技术世界&#xff01;**&#x1f389; &#x1f4d8; 博主小档案&#xff1a; 琛哥&#xff0c;一名来自世界500强的资深程序猿&#xff0c;毕业于国内知名985高校。 &#x1f527; 技术专长&#xff1a; 琛哥在深度学习任务中展现出卓越的能力&a…...

Dav_笔记14:优化程序提示 HINTs -3

查询转换的提示 以下每个提示都指示优化程序使用特定的SQL查询转换&#xff1a; ■NO_QUERY_TRANSFORMATION ■USE_CONCAT ■NO_EXPAND ■REWRITE和NO_REWRITE ■MERGE和NO_MERGE ■STAR_TRANSFORMATION和NO_STAR_TRANSFORMATION ■事实和NO_FACT ■UNNEST和NO_UNNEST…...

Makefile的用法及算法应用

编译的过程 算法&#xff1a;解决特定问题的求解步骤 算法的设计 1.正确性 语法正确合法的输入能得到合理的结果对非法的输入&#xff0c;给出满足要求的规格说明对精心选择&#xff0c;甚至刁难的测试都能正常运行&#xff0c;结果正确 2.可读性&#xff0c;便于交流&…...

伯克利 CS61A 课堂笔记 08 —— Strings and Dictionaries

本系列为加州伯克利大学著名 Python 基础课程 CS61A 的课堂笔记整理&#xff0c;全英文内容&#xff0c;文末附词汇解释。 目录 01 Strings 字符串 Ⅰ Strings are An Abstraction. Ⅱ Strings Literals have Three Forms Ⅲ String are Sequences 02 Dictionaries 字典 …...

机器学习 - 理解偏差-方差分解

为了避免过拟合&#xff0c;我们经常会在模型的拟合能力和复杂度之间进行权衡。拟合能力强的模型一般复杂度会比较高&#xff0c;容易导致过拟合。相反&#xff0c;如果限制模型的复杂度&#xff0c;降低其拟合能力&#xff0c;又可能会导致欠拟合。因此&#xff0c;如何在模型…...

Springboot引入(集成)Mybatis-plus

1、添加依赖 <!--mysql数据库--><dependency><groupId>mysql</groupId><artifactId>mysql-connector-java</artifactId><version>5.1.49</version></dependency><!--mybatis-plus--><dependency><groupI…...

stm32 lwip tcp服务端频繁接收连接失效问题解决(tcp_recved)

一、问题描述 最近用stmf429单片机作为TCP服务端遇到一个问题&#xff0c;就是客户端特别频繁的发送消息&#xff0c;过一段时间以后&#xff0c;客户端的请求不再被客户端接收到&#xff0c;而且服务器端监控的掉线回调函数也不会被调用&#xff0c;好像这个连接就凭空的消失…...

java项目之基于SSM会议管理系统的设计与实现源码(ssm+mysql)

项目简介 基于SSM会议管理系统的设计与实现实现了以下功能&#xff1a; 基于SSM会议管理系统的设计与实现的主要使用者分为&#xff1a;管理员登录后修改个人的密码。用户管理中&#xff0c;对公司内的用户进行管理&#xff0c;包括会议管理员和员工&#xff0c;管理部门信息…...

腿足机器人之二- 运动控制概览

腿足机器人之二运动控制概览 高层运动规划MPCRL 中层逆运动学和逆动力学底层执行器控制传感器校正 上一篇博客是腿足机器人的骨架和关节的机械和电气组件&#xff0c;关节不仅需要通过机械设计实现复杂的运动能力&#xff0c;还必须通过电子组件和控制系统来精确控制这些运动。…...

【MySQL】基础篇

1. MySQL中的NULL值是怎么存放的&#xff1f; MySQL的compact行格式中会用【NULL值列表】来标记值为NULL的列&#xff0c;NULL值不会存储在行格式中的真实数据部分。 NULL值列表会占用1字节空间&#xff0c;当表中所有字段都被定义成NOT NULL&#xff0c;行格式中就不会有NULL值…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...