数轴(0 ~ m)上有n个不同点,最多只能移动一个点,移动到[1, m]中任意一点,求最终最小相邻两个点的距离的最大值是什么

本文主要是介绍数轴(0 ~ m)上有n个不同点,最多只能移动一个点,移动到[1, m]中任意一点,求最终最小相邻两个点的距离的最大值是什么,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

思路:先找到相邻距离最小的位置,假设为pos, 那么不是移动第pos个点就是移动第(pos - 1)个点,先移动pos点,用数组vec存除了pos点之外的所有点,求出最小相邻距离和最大相邻距离,那么肯定将pos点插入到最大相邻距离中。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn = 1e6 + 5, inf = 1e9 + 5, maxm = 5e3 + 5, mod = 998244353;
int a[maxn];
int n, m;
string s;
int d[maxn];int calc(vector<int> vec){int mn = inf, mx = 0;for(int i = 1; i < n; i++){mn = min(mn, vec[i] - vec[i - 1] - 1);mx = max(mx, vec[i] - vec[i - 1] - 1);}return min(mn, max((mx - 1) / 2, m - vec[n - 1] - 1));
}void solve()
{cin >> n >> m;a[0] = 0;int mn = inf, mx = 0;int pos;for(int i = 1; i <= n; 

这篇关于数轴(0 ~ m)上有n个不同点,最多只能移动一个点,移动到[1, m]中任意一点,求最终最小相邻两个点的距离的最大值是什么的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/645187

相关文章

mybatis-plus如何根据任意字段saveOrUpdateBatch

《mybatis-plus如何根据任意字段saveOrUpdateBatch》MyBatisPlussaveOrUpdateBatch默认按主键判断操作类型,若需按其他唯一字段(如agentId、pe... 目录使用场景方法源码方法改造首先在service层定义接口service层接口实现总结使用场景my

JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法

《JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法》:本文主要介绍JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法,每种方法结合实例代码给大家介绍的非常... 目录引言:为什么"相等"判断如此重要?方法1:使用some()+includes()(适合小数组)方法2

Python中经纬度距离计算的实现方式

《Python中经纬度距离计算的实现方式》文章介绍Python中计算经纬度距离的方法及中国加密坐标系转换工具,主要方法包括geopy(Vincenty/Karney)、Haversine、pyproj... 目录一、基本方法1. 使用geopy库(推荐)2. 手动实现 Haversine 公式3. 使用py

把Python列表中的元素移动到开头的三种方法

《把Python列表中的元素移动到开头的三种方法》在Python编程中,我们经常需要对列表(list)进行操作,有时,我们希望将列表中的某个元素移动到最前面,使其成为第一项,本文给大家介绍了把Pyth... 目录一、查找删除插入法1. 找到元素的索引2. 移除元素3. 插入到列表开头二、使用列表切片(Lis

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

Java计算经纬度距离的示例代码

《Java计算经纬度距离的示例代码》在Java中计算两个经纬度之间的距离,可以使用多种方法(代码示例均返回米为单位),文中整理了常用的5种方法,感兴趣的小伙伴可以了解一下... 目录1. Haversine公式(中等精度,推荐通用场景)2. 球面余弦定理(简单但精度较低)3. Vincenty公式(高精度,

双系统电脑中把Ubuntu装进外接移动固态硬盘的全过程

《双系统电脑中把Ubuntu装进外接移动固态硬盘的全过程》:本文主要介绍如何在Windows11系统中使用VMware17创建虚拟机,并在虚拟机中安装Ubuntu22.04桌面版或Ubunt... 目录一、首先win11中安装vmware17二、磁盘分区三、保存四、使用虚拟机进行系统安装五、遇见的错误和解决

使用FileChannel实现文件的复制和移动方式

《使用FileChannel实现文件的复制和移动方式》:本文主要介绍使用FileChannel实现文件的复制和移动方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录使用 FileChannel 实现文件复制代码解释使用 FileChannel 实现文件移动代码解释