【洛谷 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

思路

首先从输入中读取牛棚数量 n n n和牛的数量 c c c,然后读取每个牛棚的位置,并将它们存储在数组 a a a中。对数组进行排序,确保牛棚的位置是按照从小到大的顺序排列。

定义一个check函数,用于检查给定的最小距离 x x x是否可行。函数通过遍历每个牛棚,计算相邻牛棚的距离,并累加这些距离。每当累加的距离大于或等于 x x x时,就将牛的数量增加一,并将累加的距离重置为0。最后,如果牛的数量大于或等于 c c c,则返回真,否则返回假。

main函数中,定义了两个变量 l l l r r r,分别表示最小距离的可能范围。开始时, l l l设置为0, r r r设置为一个非常大的数(INF)。然后进行二分搜索,每次取 l l l r r r的中点作为检查的最小距离,如果check函数返回真,说明当前的最小距离可行,但可能存在更大的最小距离,因此将 l l l设置为中点;否则,说明当前的最小距离不可行,可能需要减小最小距离,因此将 r r r设置为中点。重复这个过程,直到 l l l r r r的差距小于1。

在循环结束时,l 是最后一个满足条件的值,而 r 是第一个不满足条件的值。由于目标是找到满足条件的最大值,所以选择输出 l,即满足条件的最大最小距离。


AC代码

#include <algorithm>
#include <iostream>
#define INF 0x3f3f3f3f
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e5 + 7;

int n, c;
int a[N];

bool check(int x) {
	int i = n;
	int d = 0;
	int cnt = 1;
	for (int i = 2; i <= n; i++) {
		d += a[i] - a[i - 1];
		if (d >= x) {
			cnt++;
			d = 0;
		}
	}
	// cout << cnt << endl;
	return cnt >= c;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> c;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int l = 0;
	int r = INF;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			// 牛偏多,增大距离
			l = mid;
		} else {
			// 牛偏少,缩小距离
			r = mid;
		}
		// cout << l << " " << r << endl;
	}
	cout << l << endl;
	return 0;
}

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

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

相关文章

【算法面试题】-05

智能成绩表 class Student:def __init__(self):self.name "" # 学生名字self.scores [] # 每门课成绩students [Student() for _ in range(10004)] # 存储学生信息的数组 key_index 0 # 要排序的课程名的下标# 自定义排序函数 def student_comparator(a, b):…

07 数据结构之图

# Makefile CCgcc CFLAGS -g -Wall SRCStest.c graph.c link_queue.c OBJS$(SRCS:.c.o) #variable replace APPtestall:$(OBJS) #指定一个目标&#xff0c; 不然默认目标不会检查依赖文件的时间戳$(CC) $(SRCS) -o $(APP) .PH…

协程库项目—协程类模块

ucontext_t结构体、非对称协程 协程类 ucontext_t结构体 头文件中定义的四个函数&#xff08;getcontext(), setcontext(), makecontext(), swapcontext()&#xff09;和两个结构类型&#xff08;mcontext_t, ucontext_t&#xff09;在一个进程中实现用户级的线程切换。 其中…

NXP iMX8MM Cortex-M4 核心 GPT Capture 测试

By Toradex秦海 1). 简介 NXP i.MX8 系列处理器均为异构多核架构 SoC&#xff0c;除了可以运行 Linux 等复杂操作系统的 Cortax-A 核心&#xff0c;还包含了可以运行实时操作系统比如 FreeRTOS 的 Cortex-M 核心&#xff0c;本文就演示通过 NXP i.MX8MM 处理器集成的 Cortex-…

brpc之Channel

简介 Channel是brpc的通信类&#xff0c;继承于RpcChannel&#xff0c;RpcChannel是protobuf中的类&#xff0c;用于服务通信 Channel #mermaid-svg-HdRl5ZFGKiLhYVuW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-s…

Sqllab第一关通关笔记

知识点&#xff1a; 明白数值注入和字符注入的区别 数值注入&#xff1a;通过数字运算判断&#xff0c;1/0 1/1 字符注入&#xff1a;通过引号进行判断&#xff0c;奇数个和偶数个单引号进行识别 联合查询&#xff1a;union 或者 union all 需要满足字段数一致&…

《领导的气场——8堂课讲透中国式领导智慧》读书笔记

整体感悟 个人感觉书籍比较偏说教、理论&#xff0c;没有看完。 现仅仅摘录自己“心有戚戚焉”的内容。 经典摘录 管理的本质是通过别人完成任务。有一百件事情&#xff0c;一个人都做了&#xff0c;那只能叫勤劳&#xff1b;有一百件事情&#xff0c;主事的人自己一件也不做&…

子类的继承性

继承性 类有两种重要的成员&#xff1a; 成员变量和方法 子类的成员 ① 自己声明定义 ②从父类继承 ① 成员变量的继 把继承来的变量作为 自己的一个成员变量 &#xff08;如同在子类中直接声明一样&#xff09;&#xff1b; 可被子类中自定义的任何实例方法操作 。 ② 方法…

虚拟机中安装Win98

文章目录 一、下载Win98二、制作可启动光盘三、VMware中安装Win98四、Qemu中安装Win981. Qemu的安装2. 安装Win98 Win98是微软于1998年发布的16位与32位混合的操作系统&#xff0c;也是一代经典的操作系统&#xff0c;期间出现了不少经典的软件与游戏&#xff0c;还是值得怀念的…

【牛客】CM26 二进制插入 HJ60 查找组成一个偶数最接近的两个素数

目录 题目一&#xff1a;二进制插入 题目链接&#xff1a;二进制插入_牛客题霸_牛客网 (nowcoder.com) 解题思路&#xff1a; 代码实现&#xff1a; 题目二&#xff1a;查找组成一个偶数最接近的两个素数 题目链接&#xff1a;查找组成一个偶数最接近的两个素数_牛客题霸_…

【sgPhotoPlayer】自定义组件:图片预览,支持点击放大、缩小、旋转图片

特性&#xff1a; 支持设置初始索引值支持显示标题、日期、大小、当前图片位置支持无限循环切换轮播支持鼠标滑轮滚动、左右键、上下键、PageUp、PageDown、Home、End操作切换图片支持Esc关闭窗口 sgPhotoPlayer源码 <template><div :class"$options.name"…

线程和进程

参考链接&#xff1a; 1.基本概念 进程&#xff1a;Windows系统中&#xff0c;一个运行的xx.exe就是一个进程。例如打开浏览器就是一个进程 线程&#xff1a;进程中的一个执行任务&#xff08;控制单元&#xff09;&#xff0c;负责当前进程中程序的执行。一个进程至少有一个…

无人机|LQR控制算法及其无人机控制中的应用仿真

前言 LQR全称Linear Quadratic Regulator&#xff08;线性二次调节器&#xff09;&#xff0c;顾名思义用于解决形如 x ˙ A x B u y C x D u \begin{aligned}\dot{x}&AxBu\\y&CxDu\end{aligned} x˙y​AxBuCxDu​ 线性时不变系统的一种线性控制方法&#xff0c;…

初识REDHAWK

文章目录 前言一、什么是 REDHAWK?1、概述2、REDHAWK 的应用 二、REDHAWK 的流程管理和交互方法1、流程管理2、数据传输 三、入门1、安装 REDHAWK2、IDE 快速入门①、启动 REDHAWK IDE②、打开 Chalkboard③、创建信号发生器④、测试组件的输入/输出响应 前言 REDHAWK 是一个…

Opencv 绘制线段、矩形、圆形、多边形操作

1、前言 OpenCV提供了许多用于绘制图形的方法 包括绘制线段的line()方法、绘制矩形的 rectangle()方法、绘制圆形的 circle()方法、绘制多边形的 polylines()方法和绘制文字的 putText()方法 本章将依次对上述各个方法进行讲解&#xff0c;并作出相应实验。 因为 OpenCV 中的…

简洁的链式思维(CCoT)提示

原文地址&#xff1a;Concise Chain-of-Thought (CCoT) Prompting 传统的CoT导致了输出令牌使用的增加&#xff0c;而CCoT提示是一种旨在减少LLM响应的冗长性和推理时间的提示工程技术。 2024 年 1 月 24 日 Areas where Chain-Of-Thought-like methodology has been introd…

【C/C++ 学习笔记】函数

【C/C 学习笔记】函数 视频地址: Bilibili 函数结构 返回值类型函数名参数列表函数体语句return 表达式 返回值类型 函数名 (参数列表) {函数体语句;return 表达式; }声明 在函数定义之前声明函数&#xff0c;可以声明多次&#xff0c;但是只能定义依次 返回值类型 函数名…

计算机考研|保姆级择校+资料+全年规划

本科211&#xff0c;研究生上岸某985 计算机考研备考过程中走了不少弯路&#xff0c;希望我的经验能够帮助大家少走弯路 大家决定考研之前&#xff0c;一定要认真思考自己考研的目的是什么&#xff0c;有的人是随大流&#xff0c;别人考研&#xff0c;就跟风考研&#xff0c;有…

JDK 17:Java生态系统的最新巨擘

JDK 17&#xff1a;Java生态系统的最新巨擘 &#x1f680; JDK 17&#xff1a;Java生态系统的最新巨擘 &#x1f680;摘要 &#x1f31f;引言 &#x1f308;模块一&#xff1a;性能优化与提升 &#x1f527;垃圾回收器的改进&#xff1a;JIT编译器的优化&#xff1a;其他性能优…

Visual Basic6.0零基础教学(2)—vb中类的介绍和基本控件的属性

Visual Basic 6.0中类的介绍和基本控件的属性 文章目录 Visual Basic 6.0中类的介绍和基本控件的属性前言一、对象的有关概念1.类2.对象3.对象的三要素4.5. VB程序的执行步骤 二、基本控件属性1.修改控件属性的练习案例 总结 前言 大家好&#xff0c;昨天我们学习了vb的简单介…