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

算法题（139）：牛可乐和魔法封印

news 来源：原创 2025/8/22 20:53:15

审题：
本题需要我们将数组中包含在区间x~y之间的数据个数找到并输出

思路：
方法一：暴力解法

首先我们可以直接遍历一次数组，找到x的索引，然后再找到y的索引，并计算最终的元素个数，这里就要有O（n）的时间复杂度，且由于是多组数据又要进行q次。综上，时间复杂度为O（nq），而n为1e5,q为1e5，运行次数就要达到1e10.一定会超时

方法二：二分查找

对于左边界，我们可以将数组划分为小于x和大于等于x的区域。对于右边界，我们可以将数组划分为大于y和小于等于y的区域。

这就说明数组的划分具有二段性，此时我们就可以分贝对x和y进行二分查找了

对于寻找大于等于x的左边界：
1.mid的计算：(left+right)/2

因为是要让right靠近left寻找左边界

2.更新策略：
当a[mid]小于x的时候，说明mid前面包含自身的索引区域都不是左边界的候选区域了，直接让left=mid+1.

当a[mid]大于等于x的时候，虽然mid右边区域是大于等于x边界的区域，但是一定不是最左的边界了，所以让right = mid，之所以不能等于mid-1，是因为mid有可能是左边界

3.尾处理

若最终left等于right后的索引对应的数据值是小于x的，说明数组中所有数据的值都是小于x的，此时一定没有数据落在我们的x~y区间中，直接输出0，然后进入下一组判断即可

对于寻找小于等于y的右边界：
1.mid的计算：(left+right+1)/2

2.更新策略：原理与左边界查找一样

3.尾处理：判断a[left]是否大于y，若大于说明数组中没有数据落在区间x~y之间，也是输出0并进行下一组判断

解题：
 

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,q;
int a[N];
int x,y;
int main()
{//数据录入cin >> n;for(int i = 0; i < n; i++){cin >> a[i];}cin >> q;//多组数据二分查找while(q--){cin >> x >> y;int mid = 0;//查找大于等于x的左边界int pos1 = 0;//左边界ll left = 0;ll right = n-1;while(left < right){mid = (left+right)/2;if(a[mid] >= x){right = mid;}else{left = mid + 1;}}if(a[left] < x)//所有元素都小于x{cout << 0 << endl;continue;}else{pos1 = left;}//查找小于等于y的右边界int pos2 = 0;//右边界left = 0;right = n-1;while(left < right){mid = (left+right+1)/2;if(a[mid] <= y){left = mid;}else{right = mid - 1;}}if(a[left] > y)//所有元素都大于y{cout << 0 << endl;continue;}else{pos2 = left;}cout << pos2-pos1+1 << endl;}return 0;
}

若是正常的找到左右边界就用pos1或pos2记录下来最后进行计算然后输出

牛可乐和魔法封印

相关文章：

算法题（139）：牛可乐和魔法封印

审题&#xff1a; 本题需要我们将数组中包含在区间x~y之间的数据个数找到并输出 思路&#xff1a; 方法一&#xff1a;暴力解法 首先我们可以直接遍历一次数组&#xff0c;找到x的索引&#xff0c;然后再找到y的索引&#xff0c;并计算最终的元素个数&#xff0c;这里就要有O&a…...

编程日记 2025/8/22 20:53:15

LeetCode热题100--189.轮转数组--中等

1. 题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,…...

编程日记 2025/8/22 13:13:15

DeepSeek-Prover-V2：数学定理证明领域的新突破

前言 在人工智能飞速发展的当下&#xff0c;模型的迭代与创新层出不穷。 五一假期期间&#xff0c;DeepSeek 再次发力&#xff0c;推出了令人瞩目的新模型 ——DeepSeek-Prover-V2。 与大众期待的 R2 通用推理模型不同&#xff0c;这次 DeepSeek 将目光聚焦于数学定理证明领…...

编程日记 2025/8/22 20:53:12

调试——GDB、日志

调试——GDB、日志 1. gdb常用指令2. 如何生成core文件并调试&#xff1f;3. 如何调试正在运行的程序4. 调试多进程程序5. 调试多线程程序6. log日志 gcc编译器可以帮我们发现语法错误&#xff0c;但是对业务逻辑错误却无能为力。当我们想找出逻辑错误时&#xff0c;就需要调试…...

编程日记 2025/8/22 20:36:14

ARM子程序调用与返回

子程序&#xff08;也叫过程、函数、方法&#xff09;是一个能被调用和执行并返回到调用点那条指令的代码 段。 两个问题&#xff1a;如何将参数传递给子程序或从子程序中传递出来&#xff1f;怎么从子程序返回到调用点&#xff1f; 指令BSR Proc_A调用子程序Proc_A。 处理器将…...

编程日记 2025/8/22 20:36:13

WSL 安装 Debian 后，apt get 如何更改到国内镜像网址？

提问&#xff1a;Debian apt install 如何更改到国内镜像网址&#xff1f; 在 Debian 系统中&#xff0c;你可以通过修改 /etc/apt/sources.list 文件&#xff0c;将软件源更改为国内镜像网址&#xff0c;以加快软件包的下载速度。下面为你详细介绍操作步骤&#xff1a; 1. 备…...

编程日记 2025/8/22 20:39:46

SpringCloud GateWay网关

1、网关介绍 微服务网关&#xff08;Microservices Gateway&#xff09;是微服务架构中的核心组件&#xff0c;充当所有客户端请求的统一入口&#xff0c;负责请求的路由、过滤和聚合等操作。它是微服务与外部系统&#xff08;如Web、移动端&#xff09;之间的中间层&#xff0…...

编程日记 2025/8/22 20:39:46

可视化大屏开发全攻略：技术与实践指南

引言 在数字化浪潮席卷全球的当下&#xff0c;数据已成为企业乃至整个社会发展的核心驱动力。从繁华都市的交通管控中心&#xff0c;到大型企业的数据运营中枢&#xff0c;可视化大屏无处不在&#xff0c;以直观、震撼的方式展示着数据的魅力与价值。它就像是一扇通往数据世界…...

编程日记 2025/8/22 20:40:54

如何设计一个为QStackWidget的界面切换动画？

目录 前言 接口考虑 实现的思路 前言 笔者这段时间沉迷于给我的下位机I.MX6ULL做桌面&#xff0c;这里抽空更新一下QT的东西。这篇文章是跟随CCMoveWidget一样的文章&#xff0c;尝试分享自己如何书写这份代码的思考的过程 接口考虑 笔者不太想使用继承的方式重新写我们的…...

编程日记 2025/8/22 20:53:11

LeetCode 0790.多米诺和托米诺平铺：难想条件的简单动态规划

【LetMeFly】790.多米诺和托米诺平铺&#xff1a;难想条件的简单动态规划 力扣题目链接&#xff1a;https://leetcode.cn/problems/domino-and-tromino-tiling/ 有两种形状的瓷砖&#xff1a;一种是 2 x 1 的多米诺形&#xff0c;另一种是形如 "L" 的托米诺形。两种…...

编程日记 2025/8/22 20:38:10

模拟芯片设计中数字信号处理一些常用概念（一）

模拟芯片设计中经常用时域场景思考来解决问题，但实际上很多地方如果采用频域角度思考，解决问题更快更方便。 时域和频域的对照关系如下： a、如果时域信号是周期的，那么它的频谱就是离散的。 b、如果时域信号是非周期的，那么它的频谱就是连续的。 c、如果时域信号是离散的…...

编程日记 2025/8/22 20:41:24

c++进阶——AVL树主要功能的模拟实现(附带旋转操作讲解)

文章目录 AVL树的实现AVL树的概念及引入AVL树调整问题AVL树的实现AVL树的结构AVL树的插入插入的流程更新平衡因子的原则实现插入的基本框架(插入 调整平衡因子)旋转操作右单旋左单旋左右双旋右左双旋 合并旋转代码 测试部分平衡检测接口测试用例 对于其他接口的说明 AVL树的实…...

编程日记 2025/8/22 20:36:12

一个电商场景串联23种设计模式：创建型、结构型和行为型

理解了&#xff01;你希望有一个具体的项目案例&#xff0c;能够涵盖所有23种设计模式&#xff0c;并且将它们分类为创建型、结构型和行为型。这个需求非常好&#xff0c;能够帮助你从实际的应用场景理解每种设计模式的用法。 为了实现这个目标&#xff0c;我将为你设计一个电…...

编程日记 2025/8/22 20:38:10

浅拷贝和深拷贝的区别

Person p1 new Person(10);Person p2 p1;p2.age 20;System.out.println(p1p2); // trueSystem.out.println(p1.age); // 20 这种做法只是复制了对象的地址&#xff0c;即两个变量现在是指向了同一个对象&#xff0c;任意一个变量&#xff0c;操作了对象的属性&#xff0c;都…...

编程日记 2025/8/20 7:22:20

Java开发者面试实录：微服务架构与Spring Cloud的应用

面试场景 面试官: 请介绍一下你的基本情况。 程序员: 大家好&#xff0c;我叫张小明&#xff0c;今年27岁&#xff0c;硕士学历&#xff0c;拥有5年的Java后端开发经验。主要负责基于Spring Boot开发企业级应用&#xff0c;以及微服务架构的设计和实现。 面试官: 好的&#…...

编程日记 2025/8/20 7:22:19

在Ubuntu系统中安装桌面环境

在 Ubuntu 系统中安装桌面环境可以通过包管理器 apt 或工具 tasksel 实现。以下是详细的安装方法和常见桌面环境的选择&#xff1a; --- ### **1. 准备系统更新** 在安装前&#xff0c;建议更新软件源和系统包&#xff1a; bash sudo apt update && sudo apt upgrade…...

编程日记 2025/8/20 7:22:17

多语言笔记系列：Polyglot Notebooks 中使用 xUnit 单元测试

Polyglot Notebooks 中使用 xUnit 单元测试 本文目录 Polyglot Notebooks 中使用 xUnit 单元测试[TOC](本文目录)Polgylot Notebooks 并没有直接支持单元测试框架。不能像VS里那样方便的进行单元测试。简单远行的话&#xff0c;可以使用下面的方案&#xff01;1、引入必要的NuG…...

编程日记 2025/8/20 7:22:15

Cisco Packet Tracer 选项卡的使用

目录 设备Config选项卡的使用 Realtime and Simulation模式&#xff08;数据包跟踪与分析&#xff09; 设备Desktop选项卡的使用 设备Config选项卡的使用 Hostname NVRAM Startup Config----Load 加载 INTERFACE 点击on Save 如果&#xff0c;不把Running Config保存为Sta…...

编程日记 2025/8/20 7:22:14

杨校老师竞赛课之C++备战蓝桥杯初级组省赛

目录 1. 灯塔 题目描述 输入描述 输出描述 输入样例1 输出样例1 输入样例2 输出样例2 数据说明 2. 子区间 题目描述 输入描述 输出描述 输入样例 输出样例 数据说明 3. 染色 题目描述 输入描述 输出描述 输入样例1 输出样例1 输入样例2 输出样例2 数据…...

编程日记 2025/8/20 7:22:12

gcc/g++用法摘记

链接静态库 gcc main.o -L/path/to/libs -lmylib -o myprogram 【待续】...

编程日记 2025/8/20 7:22:10

kotlin 扩展函数

Kotlin 扩展函数的定义与使用 定义扩展函数 Kotlin 的扩展函数是一种强大的机制&#xff0c;允许开发者为已有的类添加额外的功能&#xff0c;而无需继承该类或对其进行任何修改。这种特性极大地提高了代码的灵活性和可读性。 扩展函数可以通过在函数名称前指定目标类型的接…...

编程日记 2025/8/21 9:00:08

机器人强化学习入门学习笔记

（1）物理引擎 物理引擎就是模拟真实世界物理规律的软件工具。它会根据你给定的物体、质量、形状、力等信息，计算这些物体在时间上的运动和相互作用。如果你设计了一个机器人，那物理引擎就是“虚拟现实世界”，让机器人在里面“活起来”，模拟它走路、抓东西、摔倒等动作。而…...

编程日记 2025/8/20 7:22:07

《RESTful API版本控制的哲学思辨：稳定性与创新性的终极平衡》

有效的版本控制&#xff0c;就如同精密仪器中的校准装置&#xff0c;确保API在不断升级的过程中&#xff0c;依然能与旧有系统无缝对接&#xff0c;维持整个生态的平稳运行。 不同的客户端对API的依赖程度和使用方式各不相同。有些客户端可能因为各种原因&#xff0c;无法及时…...

编程日记 2025/8/21 14:25:50

spring中spring-boot-configuration-processor的使用

spring-boot-configuration-processor 是 Spring Boot 提供的注解处理器&#xff0c;用于在编译阶段生成配置元数据文件&#xff08;spring-configuration-metadata.json&#xff09;&#xff0c;从而优化开发体验。以下是其核心功能和使用指南&#xff1a; 一、核心功能 IDE 智…...

编程日记 2025/8/19 8:57:37

30天开发操作系统 第27天 -- LDT与库

前言 大家早上好&#xff0c;我们今天的第一个任务就是修复昨天晚上的那个bug。是个什么bug来着&#xff1f;就是用nsct命令运行的应用程序&#xff0c;无论是按ShiftF1还是点击窗口的“x”按钮都没有反应的那个bug啦。 我们得先来找到出问题的原因&#xff0c;然后才能采取对…...

编程日记 2025/8/20 10:03:47

std::move()详解

一、std::move()的作用和原理 本质&#xff1a; std::move()并不像字面意思“搬走”那些对象&#xff0c;而是&#xff1a; 将传入的对象“强制转化”为右值引用类型&#xff0c;从而开启“移动语义”。 在源码层面&#xff1a; 复制代码 template<typename T> std::…...

编程日记 2025/8/20 4:19:39

linux系统基本操作命令

文件和目录操作 ls&#xff1a;列出目录内容。 例如&#xff1a;ls -l 显示详细信息&#xff0c;ls -a 显示包括隐藏文件在内的所有文件。 cd&#xff1a;改变当前目录。 例如&#xff1a;cd /home/username 切换到指定目录。 pwd&#xff1a;显示当前目录的完整路径。 mk…...

编程日记 2025/8/22 8:18:08

python打卡day16

NumPy 数组基础 因为前天说了shap&#xff0c;这里涉及到数据形状尺寸问题&#xff0c;所以需要在这一节说清楚&#xff0c;后续的神经网络我们将要和他天天打交道。 知识点&#xff1a; numpy数组的创建&#xff1a;简单创建、随机创建、遍历、运算numpy数组的索引&#xff1a…...

编程日记 2025/8/22 10:19:04

架构进阶：什么是数据架构，如何理解数据架构？（华为）

数据架构是企业架构的重要组成部分，DAMA、IBM 及国内大厂对其定义各有侧重。它包含数据资产目录、数据标准、数据模型和数据分布四个组件。数据资产目录可梳理企业数据资产，数据标准统一数据含义和规则，数据模型反映业务对象关联关系，数据分布呈现数据流动情况。数据架构是…...

编程日记 2025/8/20 7:22:00

基于EFISH-SCB-RK3576工控机/SAIL-RK3576核心板的KTV点歌主机技术方案‌（国产化替代J1900的全场景技术解析）

‌一、硬件架构设计‌ ‌多媒体处理模块‌ ‌超高清解码‌&#xff1a; RK3576 NPUGPU协同解码&#xff0c;支持4K60fps H.265硬解&#xff08;功耗<5W&#xff09;&#xff0c;支持8路1080P视频同步预览对比J1900需外接VPU解码芯片&#xff0c;硬件成本降低40%&#xff0c;…...

编程日记 2025/8/22 16:07:38

Java面试深度解密：Spring Boot、Redis、日志优化、JUnit5及Kafka事务核心技术解析

模拟面试实战 面试官&#xff1a;请解释Spring Boot的自动配置原理&#xff1f;哪些关键注解参与了这一过程&#xff1f; xbhog&#xff1a;Spring Boot通过AutoConfiguration标记核心配置类&#xff0c;通过ConditonalOnClass和ConditionalOnMissingBean判断依赖是否存在并自…...

编程日记 2025/8/19 18:09:53

内存碎片深度剖析

目录 什么是内存碎片 内部碎片的解决 malloc STL二级空间配置器 外部碎片的解决 伙伴系统算法 slab分配器 什么是内存碎片 内存碎片是指在内存中存在的一些不连续的、较小的空闲内存块&#xff0c;这些小块内存由于太小而无法被有效地分配给程序使用&#xff0c;从而导…...

编程日记 2025/8/19 21:07:41

飞帆网页中使用 i 评论插件

https://fvi.cn/786...

编程日记 2025/8/22 5:44:47

DeepSeek成本控制的三重奏

知识蒸馏 使用规则引擎筛选合成数据&#xff0c;来替代90%的人工标注 动态精度切换&#xff1a;“节能模式” 根据任务复杂度自动切换FP16/INT8精度&#xff0c;单位token能耗低至0.0028瓦时&#xff0c;推理电费成本降低82% 极致压缩训练 通过以上的技术&#xff0c;降低训练…...

编程日记 2025/8/19 15:07:41

五一の自言自语 2025/5/5

今天开学了&#xff0c;感觉还没玩够。 假期做了很多事&#xff0c;弄了好几天的路由器、监控、录像机&#xff0c;然后不停的出现问题&#xff0c;然后问ai&#xff0c;然后解决问题。这次假期的实践&#xff0c;更像是计算机网络的实验&#xff0c;把那些交换机&#xff0c;…...

编程日记 2025/8/20 7:21:52

效整理文件信息！一键生成文件夹目录的工具

一、软件介绍 大家好&#xff0c;今天给大家推荐一款实用的文件夹目录生成工具&#xff0c;它能快速提取文件夹内的文件信息&#xff0c;并整理成Excel表格&#xff0c;包含文件名、路径、类型、创建/修改时间、大小等关键数据。 为什么需要这个工具&#xff1f; 之前我想整理…...

编程日记 2025/8/22 2:18:00

关闭ollama开机自启动

不同操作系统关闭Ollama开机自启动的方法有所不同&#xff0c;以下是常见操作系统的具体方法&#xff1a; Windows系统 通过任务管理器&#xff1a;按Ctrl Shift Esc打开任务管理器&#xff0c;切换到“启动”选项卡&#xff0c;在列表中找到Ollama&#xff08;或相关条目&a…...

编程日记 2025/8/20 10:03:45

2025 年最新树莓派 Pico 连接 ESP8266 模块实现 WiFi 通信、搭建 TCP 服务器实现数据交互详细教程

AT 指令基本结构概述 AT 指令最初由 Hayes 公司为其调制解调器&#xff08;modem&#xff09;开发&#xff0c;目的是提供一种标准化的方式来控制通信设备。最早的 Hayes Smartmodem 300 调制解调器&#xff08;1981年&#xff09;引入了这一指令集&#xff0c;因此 AT 指令也…...

编程日记 2025/8/19 18:46:19

java类=null的回收

在Java&#xff08;或类似使用垃圾回收的语言&#xff09;中&#xff0c;当你执行 a null 后&#xff0c;对象 B() 是否会被回收取决于是否还有其他引用指向它。具体分析如下&#xff1a; 关键点&#xff1a; 引用链分析&#xff1a; 初始时&#xff1a;a 引用了 A 实例&#…...

编程日记 2025/8/21 21:35:38

2025系统架构师---论面向对象的软件设计

摘要 自“软件危机”出现过后&#xff0c;工程化软件开发方法不断发展&#xff0c;采用什么方法对大 规模软件进行设计并保证软件的质量。在这样背景下&#xff0c;人们开始从面向数据流过 程开发法中不断思考&#xff0c;进而引入对象的概念。对象是数据与行为的封装&#…...

编程日记 2025/8/20 10:03:39

如何判断node节点是否启用cgroup？

要判断 Linux 节点是否启用了 cgroup&#xff08;Control Groups&#xff09;&#xff0c;可以通过以下方法验证&#xff1a; 方法 1&#xff1a;检查 /proc/cgroups 文件 查看内核支持的 cgroup 子系统列表&#xff1a; cat /proc/cgroups 输出说明&#xff1a; 若文件不存…...

编程日记 2025/8/20 9:06:33

学习黑客Nmap 实战

金丹期第三重 — Debian 12 实战&#xff1a;Nmap 全流程探秘 testhtml5.vulnweb.com 晋阶宣言 本章彻底补完前面“只扫到 80/443 却没识别 nginx 版本”的缺憾。 道友将依次完成 快速侦查 → 深度洞察 → NSE 弱点扫描 三连招&#xff0c;并学会用 -sV、-Pn、--script-trace 等…...

编程日记 2025/8/20 10:03:35

AD创建元件符号

在创建好工程文档之后打开SCH Library 创建工程的方法&#xff1a;AD创建一个工程文档-CSDN博客 这里以创建一个电容符号为例子&#xff0c;先创建引脚&#xff0c;画引脚的时候要把网格尺寸设置为100mil AD原理图怎么改网格尺寸-CSDN博客 放置好引脚之后绘制元素&#xff0…...

编程日记 2025/8/22 11:48:28

第六章：6.1 ESP32教学：多任务处理与FreeRTOS实战

一、FreeRTOS简介 ESP32内置了FreeRTOS实时操作系统内核&#xff0c;这是一个专为嵌入式系统设计的开源实时操作系统。它支持&#xff1a; 多任务并行处理 任务优先级管理 内存管理 任务间通信 定时器管理 二、任务创建与管理 1. 任务创建&#xff08;xTaskCreate&…...

编程日记 2025/8/22 16:52:20

Python生活手册-正则表达式：从快递单到咖啡订单的文本魔法

一、快递单号识别术&#xff08;基础匹配&#xff09; 1. 数字猎人&#xff08;\d&#xff09; 想象你有一叠快递单需要自动识别&#xff1a; import re快递单 "【顺丰】单号&#xff1a;SF123456789 签收人&#xff1a;张先生" 单号 re.search(r"SF\d&quo…...

编程日记 2025/8/20 10:03:29

Windows 自带删除缓存

Temp临时文件文件夹手动除 Windows键R 快速打开运行输入%temp%,其下所有文件删除 打开储存感知 打开「设置」→「系统」→「存储」&#xff0c;点击右侧面板中的「配置存储感知或立即运行」。将弹出页拉至最下方&#xff0c;勾选其中的「删除以前版本的 Windows」&#xff0c;再…...

编程日记 2025/8/20 10:03:27

Linux电源管理(6)_Generic PM之挂起功能

原文链接&#xff1a;Linux电源管理&#xff08;6&#xff09;_Generic PM之挂起功能 1.前言 Linux内核提供了三种暂停方式&#xff1a;Freeze&#xff0c;Standby和STR&#xff08;暂停到RAM&#xff09;&#xff0c;在用户空间向” / sys / power / state”文件分别写入“ …...

编程日记 2025/8/20 10:03:25

MCP原理详解及实战案例(动嘴出UI稿、3D建模)

文章目录 MCP 原理介绍架构核心组件协议层传输层连接生命周期MCP与function calling: 互补关系 MCP python SDKMCP的优点 怎么用MCP&#xff1a;天气服务参考应用项目&#xff1a; REF 24年11月份&#xff0c;claude推出了模型上下文协议( MCP),作为一种潜在的解决方案&#xf…...

编程日记 2025/8/20 10:03:23

【Java项目脚手架系列】第二篇：JavaWeb项目脚手架

【Java项目脚手架系列】第二篇&#xff1a;JavaWeb项目脚手架 前言 在Java Web开发中&#xff0c;一个好的项目脚手架可以大大提高开发效率&#xff0c;减少重复工作。本篇文章将介绍一个基于Maven的JavaWeb项目脚手架&#xff0c;它包含了基础的Web开发配置和常用功能。 什…...

编程日记 2025/8/20 10:03:21

【机器学习-线性回归-5】多元线性回归：概念、原理与实现详解

线性回归是机器学习中最基础且广泛应用的算法之一&#xff0c;而多元线性回归则是其重要扩展。本文将全面介绍多元线性回归的核心概念、数学原理及多种实现方式&#xff0c;帮助读者深入理解这一强大的预测工具。 1. 多元线性回归概述 1.1 什么是多元线性回归 多元线性回归(…...

编程日记 2025/8/20 10:03:19