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

每日算法：洛谷U535992 J-C 小梦的宝石收集（双指针、二分）

news 来源：原创 2025/9/18 3:19:40

题目描述

小梦有 n 颗能量宝石，其中第 i 颗的能量为 ai，但这些能量宝石十分不稳定，随时有可能发生崩坏，导致他们全部消失！

小梦想要留住宝石们，不希望他们发生崩坏，同时他发现：如果这些宝石的能量的极差越大，则这些宝石们越不稳定，因此他希望最小化这些宝石的能量的极差（最大值减去最小值的差值）。

小梦有一招点石成金的技能，这个技能可以以如下方式改变一些宝石的能量：

∙ 要么小梦选择一块能量最小的宝石，将他变成一块当前能量最大的宝石。

∙ 要么小梦选择一块能量最大的宝石，将他变成一块当前能量最小的宝石。

形式化的即：

∙ 选择 i (1≤i≤n,ai=min(a1,a2,...,an))，执行：ai:=max(a1,a2,...,an)。

∙ 或选择 i (1≤i≤n,ai=max(a1,a2,...,an))，执行：ai:=min(a1,a2,...,an)。

小梦至多可以使用 k 次上述的 ”点石成金“ 技能，他想知道这些宝石的能量极差最小可以变为多少，请你帮他算一算吧。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据的格式如下：

第一行两个正整数 n,k，分别表示小梦拥有的宝石数量 n ，和他最多可以释放 “点石成金” 技能的次数 k。

第二行 n 个正整数 ai，表示每块宝石的能量。

输出格式

对于每组测试数据：

在单独的一行输出一个整数，表示宝石能量的极差最小值。

输入输出样例

输入 #1

2
8 3
1 2 3 4 5 6 7 8
4 3
100 1 100 2

输出 #1

4
0

说明/提示

【样例 1 解释】

使用 3 次操作一，选择 min 变为 max，操作完后数组变成：{8,8,8,4,5,6,7,8}。

此时数组的极差为 4 最小，可以证明不存在比 4 更优的答案。

【数据范围】

令 N 表示 T 组数据中 n 的总和。

对于 30% 的数据有：T=1,1≤k≤N≤20。

对于 60% 的数据有：1≤T≤10,1≤k≤N≤2000。

对于所有的测试数据有： 1≤T≤1000,1≤N≤5×105,0≤k≤n,0≤ai≤109。

思路：

我们很容易想到，先将数组进行排序，然后分别用两个指针l，和r表示最左侧的最大值和最右侧的最小值。

每次只要有将最小值变成最大值或者将最大值变成最小值的情况出现，那么我们就需要移动左或右指针到次小或次大值的位置上。

这样，我们假设当l指针在i位置，r指针在j位置时，找到答案，则操作次数为：（i-1）【操作左边要用的次数】+（n-j）【操作右边要用的次数】+min(i-1,n-j)【将左边的值变成最大值或将右边的值变为最小值后，额外再需要移动的次数例：如果左边是1，右边是8，修改左边后，最后面的两个数应该是8,8因此如果此时要再操作右边，应该额外加上左边的操作次数，同理另一种情况也是如此，而这个值我们希望它尽可能小，这样可操作的次数就会变多】

而由题目规定，我们可知：（i-1）+（n-j）+min(i-1,n-j) <= k

因此当符合这一规定时，我们则用ans记录它的差值，取最小值。

于是我们可以很轻松的想到双重循环遍历枚举，但是双重循环肯定过不了，然后我们发现:该数组中的数是单调递增的，且满足二分性，因此我们可以将第二重循环优化为二分，这样的时间复杂度是nlogn。

代码：

#include<bits/stdc++.h>using namespace std;
int t,n,k;
const int N = 5e5+10;
int q[N];int main(){cin>>t;while(t--){cin>>n>>k;for(int i =1;i<=n;i++){cin>>q[i];}sort(q+1,q+n+1);//先从小到大排序 int ans = INT_MAX;//初始化为极大值 for(int i = 1;i<=n;i++){if(i - 1 > k) break;int l = i,r = n;//在从i到n的区间里找到右边界 if(i - 1>k) break;//操作次数超过k了，直接跳出 while(l <= r){int mid = (l+r) / 2;if((i-1) + (n - mid) + min(i-1,n-mid) <= k) r = mid-1;else l = mid+1;}ans = min(ans,q[l]-q[i]);//每次更新取最小值 }cout<<ans<<endl;}return 0;
}

每日算法：洛谷U535992 J-C 小梦的宝石收集（双指针、二分）

题目描述小梦有 n 颗能量宝石，其中第 i 颗的能量为 ai，但这些能量宝石十分不稳定，随时有可能发生崩坏，导致他们全部消失！ 小梦想要留住宝石们，不希望他们发生崩坏，同时他发现：如…...

编程日记 2025/9/18 3:19:40

写给新人的深度学习扫盲贴：ReLu和梯度

一、ReLU（Rectified Linear Unit，修正线性单元） 梯度是深度学习中最常用的激活函数之一，因其简单、高效且能有效缓解梯度消失问题而被广泛使用。 1. 数学定义函数表达式： $$ \text{ReLU}(x) \max(0, x) \begin{…...

编程日记 2025/9/10 22:56:11

Spring 框架的核心基础：IoC 和 AOP

一、IoC（Inversion of Control，控制反转） 定义： IoC（Inversion of Control，控制反转），就是把对象创建和依赖关系的管理交给 Spring 容器，而不是由程序员手动去创建对象…...

编程日记 2025/9/9 3:40:07

JavaScript逆向工程实战：如何精准定位加密参数生成位置

前言：一个令人困惑的调试案例最近在进行某网站的JavaScript逆向分析时，我遇到了一个有趣的现象：当我尝试定位一个名为m的加密参数（值为MTIwMTE3NDQxODk1NTY1NjkA这样的Base64字符串）时，调试器却带我来到了…...

编程日记 2025/9/9 4:12:02

SSM智能停车场管理系统

🍅点赞收藏关注 → 添加文档最下方联系方式咨询本源代码、数据库🍅 本人在Java毕业设计领域有多年的经验，陆续会更新更多优质的Java实战项目希望你能有所收获，少走一些弯路。🍅关注我不迷路🍅 项目视频 SS…...

编程日记 2025/8/30 6:58:06

[定位器]晶艺LA1823,4.5V~100V, 3.5A,替换MP9487,MP9486A,启烨科技

Features  4.5V to 100V Wide Input Range  3.5A Typical Peak Current Limit  Integrated 500mΩ low resistance high side power MOS.  Constant On Time Control with Constant Switching Frequency.  180μA Low Quiescent Current  150kHz/240kHz/420kHz Swi…...

编程日记 2025/9/8 0:09:50

天元证券｜A股大反攻！北证50涨超10%！芯片股大爆发

今日，A股全线走强。科技成长股领涨，北证50指数飙升逾10%，科创50也大涨超4%，深证成指、上证指数午后也稳步拉升涨逾1%。值得注意的是，上证50指数临近收盘集合竞价的时候直线拉升。近4600只个股上涨，成交稳步…...

编程日记 2025/9/13 11:56:40

利用python从零实现Byte Pair Encoding(BPE)：NLP 中的“变形金刚”

BPE：NLP 界的“变形金刚”，从零开始的奇幻之旅在自然语言处理（NLP）的世界里，有一个古老而神秘的传说，讲述着一种强大的魔法——Byte Pair Encoding（BPE）。它能够将普通的文本“变形…...

编程日记 2025/9/9 3:11:45

OpenBMC：BmcWeb 处理http请求6 调用路由处理函数

OpenBMC：BmcWeb 处理http请求5 检查权限-CSDN博客检查完权限后，调用了rule.handle(*req, asyncResp, params); template <typename... Args> class TaggedRule :public BaseRule,public RuleParameterTraits<TaggedRule<Args...>> {void handle(const Req…...

编程日记 2025/9/17 23:37:36

售货机管理系统：智慧零售时代的运营新引擎

一、引言在快节奏的都市生活中，自动售货机已成为便捷消费的重要场景。然而，传统售货机依赖人工补货、手工对账，常面临库存失衡、设备故障发现滞后、数据孤岛等痛点。如何突破效率瓶颈？本文将深入剖析榕壹云售货机管理系统的项目背景、客户定位、技术与核心功能、系统优势…...

编程日记 2025/9/12 6:00:23

Python基础全解析：从输入输出到字符编码的深度探索

一、Python程序交互的基石：Print函数详解 1.1 基础输出功能 # 输出数字 print(20.5) # 输出浮点数：20.5 print(0b0010) # 输出二进制数：10# 输出字符串 print(Hello World!) # 经典输出示例# 表达式计算 print(4 4 * (2-1)…...

编程日记 2025/9/16 1:58:31

Python第八章02：数据可视化Pyecharts包无法使用

PS:本节纯属个人在学习过程中遇到问题、解决问题的经验分享，对学习进度没影响，没有遇到该问题的小伙伴可跳过。首先，在学习数据图形化过程中，通过命令提示符安装了Pyecharts包，在命令提示符中验证安装成功。在PyChar…...

编程日记 2025/9/11 8:15:49

【人工智能】如何通过精准提示工程实现完美的珠宝首饰展示

AI艺术创作指南：如何通过精准提示工程实现完美的珠宝首饰展示引言：认知边界的突破在AI艺术创作的漫长探索中，许多创作者面临着相似的困扰：当他们看到别人能够通过算法编织出如同文艺复兴时期细腻油画般的奢华珠宝展示图&#…...

编程日记 2025/9/17 14:07:33

Redis学习总结（持续更新）

Redis 目前在学习redis，遇到的一些问题会放在这里，加深自己的印象。 1. Redis缓存相较于传统Session存储的特点 Session的存储方式： 通常，传统的Session是存储在应用服务器的内存中，比如Tomcat的Session管理器。用户…...

编程日记 2025/9/16 4:22:37

RabbitMQ从入门到实战-3(高可靠性)

文章目录发送者可靠性发送者重连发送者确认（一般不会开启）指定returncallback和confrimfallbacktips MQ可靠性数据持久化LazyQueue（默认模式且不可更改） 消费者的可靠性消费者确认机制消费者失败重试业务幂等性唯一消息id业务判断…...

编程日记 2025/9/12 20:17:23

RTK 实时动态定位概述

01 引言 RTK（实时动态定位，Real-Time Kinematic）是一种高精度的卫星导航定位技术，通过差分校正方法，将GNSS（全球导航卫星系统）的定位精度从米级提升至厘米级（通常1-3厘米），广泛应用于测绘、无人机、自动驾驶、精准农业等领域。 02 概述 1. RTK的基本原理 RTK的核…...

编程日记 2025/8/29 16:25:15

Conda 环境离线迁移实战：解决生产环境网络限制的高效方案20250409

Conda 环境离线迁移实战：解决生产环境网络限制的高效方案在生产环境无法联网的前提下，如何高效、安全地部署 Python 虚拟环境，是许多企业在实际运维中必须面对的问题。特别是当前常见的开发环境基于 Miniconda，生产环境使用 Ana…...

编程日记 2025/9/17 15:23:40

dify使用知识库

注意要用向量模型导入文件选择向量模型要下载好后，才可以导入模型， 这个模型没法在ollama中run 聊天工具添加知识库效果...

编程日记 2025/8/17 21:45:43

HTTP：一.概述

http是干嘛的？超文本传输协议（英语：HyperText Transfer Protocol，缩写：HTTP）是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP是万维网的数据通信的基础。设计HTTP最初的目的是为了提供一种发布和接收HTML页面的方法。通过HTTP或者HTTPS协议请求的资源由统…...

编程日记 2025/9/15 15:09:38

Appium工作原理及环境的搭建（1）

1、Appium的介绍： 一、什么是Appium Desktop？ Appium Desktop是Appium项目的桌面版GUI工具，提供了一个友好的界面，用于启动Appium服务器、查看设备日志、与设备交互、调试自动化脚本等。相比于命令行工具，Appium Des…...

编程日记 2025/9/16 1:58:23

Interactron: Embodied Adaptive Object Detection(训练时进行更新参数) 还没看懂

Interactron: Embodied Adaptive Object Detection 创新点这些方法通常存在两个主要的共同假设。第一，模型在固定的训练集上进行训练，并在预先录制的测试集上进行评估。第二，模型在训练阶段结束后保持冻结状态，即训练完成后不再…...

编程日记 2025/9/16 1:58:27

【Pandas】pandas DataFrame copy

Pandas2.2 DataFrame Conversion 方法描述DataFrame.astype(dtype[, copy, errors])用于将 DataFrame 中的数据转换为指定的数据类型DataFrame.convert_dtypes([infer_objects, …])用于将 DataFrame 中的数据类型转换为更合适的类型DataFrame.infer_objects([copy])用于尝试…...

编程日记 2025/9/10 14:51:25

Redis基础指令(Windows)

1.cmd命令行启动redis 直接cmd打开整个文件 1.1.启动server 输入指令： redis-server.exe redis.windows.conf 会进入serve端 1.2.启动客户端 ！！重新打开一个cmd，方法和上面一样！！ 之后输入 redis-…...

编程日记 2025/9/15 1:38:41

MV-DLS600P激光振镜立体相机（MV-DLS600P）重要参数解析

功能特性采用激光振镜技术，亚毫米级图像采集精度高能效激光模块配合精准曝光同步，性能更稳定支持多帧融合，无惧金属工件表面反光干扰支持RGB、深度图同步对齐输出，便于二次开发配备窄带滤光片，抗干扰能力更强&…...

编程日记 2025/9/12 3:28:15

C语言【输出字符串中的大写字母】

题目输出字符串中的大写字母思路（注意事项） 纯代码 #include<stdio.h> #include<string.h>int main(){char str[20], ans[20];fgets(str, sizeof(str), stdin);str[strcspn(str, "\n")] \0;for (int i 0, j 0; i < strl…...

编程日记 2025/9/13 20:40:44

UniApp基于xe-upload实现文件上传组件

xe-upload地址：文件选择、文件上传组件（图片，视频，文件等） - DCloud 插件市场致敬开发者！！！ 感觉好用的话，给xe-upload的作者一个好评背景：开发中经常会有…...

编程日记 2025/9/9 13:32:51

deque容器

1.定义也叫双端数组，可以对头部进行插入和删除。 2.与vector区别 3.内部工作原理他是把整个地址划分成多块小地址（缓冲区），然后有一个中控区去记录这些地址，然后访问的时候先通过中控区然后再转到相应的缓冲区&am…...

编程日记 2025/9/11 13:23:07

git 总结遇到的问题

git Push 报错 Push failed send-pack: unexpected disconnect while reading sideband packet Total 2269 (delta 418), reused 0 (delta 0), pack-reused 0 the remote end hung up unexpectedly 解决方案：增加 Git 的缓冲区，有时由于数据量大或网络…...

编程日记 2025/8/17 23:51:41

python基础语法11-文件读写

在 Python 中，文件操作是日常编程中的常见任务之一。Python 提供了简单且强大的工具来读取和写入文件。通过使用内置的 open() 函数、read()、readline()、write() 等方法，我们可以轻松实现对文件的操作。此外，Python 的 with 语句可以帮助我…...

编程日记 2025/9/8 15:19:58

Webstorm 使用搜不到node_modules下的JS内容 TS项目按Ctrl无法跳转到函数实现

将node_modules标记为不排除，此时要把内存改大，不然webstorm中途建立索引时，会因为内存不足，导致索引中途停止，造成后续搜索不出来更改使用内存设置内存调为4096 若出现搜不出来js内容时，请直接重启下该项…...

编程日记 2025/9/12 8:07:12

转行嵌入式，需要自学多久？

作为一个本硕都学机械，却阴差阳错进入嵌入式行业的老兵，这个问题我能聊一整天。十几年前我还在工厂车间穿着工装和机床打交道，偶然接触到单片机后就一发不可收拾。转行这条路我走得异常艰辛，踩过的坑比写过的代码还多。去年我终…...

编程日记 2025/9/15 1:38:37

BLE 协议栈事件驱动机制详解

在 BlueNRG-LP 等 BLE 系统中，事件驱动是控制状态转移、数据交互和外设协作的基础。本文将深入讲解 BLE 协议栈中事件的来源、分发流程、处理结构与实际工程实践策略，帮助你构建稳定、可维护的 BLE 系统。 📦 一、BLE 事件的来源分类 BLE 协议栈中的事件严格来自协议栈本身…...

编程日记 2025/9/16 1:31:52

AI开发学习路线（闯关升级版）

以下是一份轻松版AI开发学习路线，用「闯关升级」的方式帮你从零开始变身AI开发者，每个阶段都配有有趣的任务和实用资源，保证不枯燥、可落地！👇 目录 🔰 新手村：打基础（1-2个月&…...

编程日记 2025/9/13 21:01:32

突破，未观测地区罕见极端降雨的估计

文章中文总结（重点为方法细节） 一、研究背景与目的在无测站或短观测记录地区，传统极值理论（如GEV）难以估计稀有极端降雨事件；本文提出一种新的区域化极值估计方法：区域化 Metastatistical Ex…...

编程日记 2025/9/14 22:54:25

zk源码—4.会话的实现原理一

大纲 1.创建会话 (1)客户端的会话状态 (2)服务端的会话创建 (3)会话ID的初始化实现 (4)设置的会话超时时间没生效的原因 2.分桶策略和会话管理 (1)分桶策略和过期队列 (2)会话激活 (3)会话超时检查 (4)会话清理 1.创建会话 (1)客户端的会话状态 (2)服务端的会话创建…...

编程日记 2025/9/4 1:23:45

快排算法（分治实现）

本算法采用将整个数组划分成三个部分 <key key >key 在数组全是同一个数字时，也能达到NlogN的时间复杂度下面的板书中i为遍历数组的下标 left为<key的最右边的下标 right为>key的最左边的下标例题1：912. 排序数组 - 力扣&#xff0…...

编程日记 2025/9/4 1:22:04

P9242 [蓝桥杯 2023 省 B] 接龙数列

这道题说要求最少删多少个使剩下的序列是接龙序列，这个问题可以转换为序列中最长的接龙序列是多少，然后用总长度减去最长接龙序列的长度就可以了，在第一个暴力版本的代码中我用了两个for循环求出了所有的接龙序列的长度，但是会超时…...

编程日记 2025/9/13 1:00:59

未来 AI 发展趋势与挑战（AGI、数据安全、监管政策）

从 ChatGPT 的火爆到国内 DeepSeek、通义千问、百川智能等模型的兴起，AI 正以前所未有的速度走入各行各业。而下一阶段，AI 是否会发展出真正的“通用智能”（AGI）？数据隐私、技术伦理又该如何应对？本文将带你全面洞察未来 AI 的技术趋势与落地挑战。一、AGI 的曙光：通用…...

编程日记 2025/9/16 1:10:41

驱动开发硬核特训 · Day 6 ：深入解析设备模型的数据流与匹配机制 —— 以 i.MX8M 与树莓派为例的实战对比

🔍 B站相应的视屏教程： 📌 内核：博文视频 - 从静态绑定驱动模型到现代设备模型主题：深入解析设备模型的数据流与匹配机制 —— 以 i.MX8M 与树莓派为例的实战对比在上一节中，我们从驱动框架的历史演进出…...

编程日记 2025/9/15 11:10:39

MyBatis 动态 SQL 使用详解

🌟 一、什么是动态 SQL？ 动态 SQL 是指根据传入参数，动态拼接生成 SQL 语句，不需要写多个 SQL 方法。MyBatis 提供了 <if>、<choose>、<foreach>、<where> 等标签来实现这类操作 ✅ 二、动态 SQL 的优点…...

编程日记 2025/9/12 16:50:48

数据结构实验4.1：链队列的基本操作

文章目录一，问题描述二，基本要求三，算法分析链队列的存储结构设计基本操作的算法分析四，示例代码五，实验操作六，运行效果一，问题描述编程实现有关链队列的下列基本操作。 （1&am…...

编程日记 2025/9/13 22:38:17

独立部署及使用Ceph RBD块存储

Ceph RBD（RADOS Block Device） 是 Ceph 分布式存储系统中的块存储组件，类似于 AWS EBS、iSCSI 等。它独立于 OpenShift 或 IBM CP4BA，是一个分布式存储系统，提供高性能、可扩展性和容错能力，适用于数据库、…...

编程日记 2025/9/12 9:20:25

C++初阶-C++入门基础

目录编辑 1.C的简介 1.1C的产生和发展 1.2C的参考文档 1.3C优势和难度 1.4C学习的建议 2.C的第一个程序 2.1打印Hello world 2.2头文件 2.3namespace命名空间 2.4：：作用域限定符 2.5namespace的延伸 2.6C的输入输出 3.总结 1.C的简介 …...

编程日记 2025/9/15 1:29:19

部署大模型不再难：DeepSeek + 腾讯云 HAI 实战教程

网罗开发 （小红书、快手、视频号同名） 大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/9/15 0:04:22

算法训练之位运算

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ ✨✨✨✨✨✨ 个…...

编程日记 2025/9/16 1:58:29

初识Linux：常见指令与权限的理解，以及相关衍生知识

目录前言关于linux的简介代码开源网络功能强大系统工具链完整一、Linux下的基本指令 1.ls指令 2.pwd指令 3.cd指令 4.whoami指令 5.touch指令 6.mkdir指令 7.rm指令 8.man指令 9.cp指令 10.mv指令 11.nano指令 12.cat指令 13.tac指令 14.more指令 15.less指令 16.head指令…...

编程日记 2025/9/15 20:14:05

PostgreSQL-数据库的索引 pg_operator_oid_index 损坏

报错信息： 连接测试失败 Error connecting to database: Connection failed: ERROR: index "pg_operator_oid_index" contains unexpected zero page at block 3 Hint: Please REINDEX it. 这个错误表明 PostgreSQL 数据库的索引 pg_operator_oid_index …...

编程日记 2025/9/10 3:55:34

数字图像处理作业4

数字图像处理作业4 Project 4：Image Restoration The scoring method for this project is as follows： 1．Implement a blurring filter using the equation（5．6－11，数字图像处理（…...

编程日记 2025/9/7 15:30:05

Simulink中Signal Builder在新版中找不到怎么办

在较新的MATLAB版本中，新版Simulink中的Signal Builder用Signal Editor作为替代工具。 signal builder not shown in matlab - MATLAB Answers - MATLAB Central signalBuilderToSignalEditor 1.打开上面第二个链接 2.点击拷贝 3.然后在命令行中粘贴 4.然后就会…...

编程日记 2025/9/16 4:18:35

题目描述

输入格式

输出格式

输入输出样例

说明/提示

相关文章：