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

AcWing907. 区间覆盖

参考的视频讲解:↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
【贪心算法08-区间问题03-区间覆盖】
每次贪心就是选择左端点里面<起始端点里面右边界最大的,这样就是保证了最少区间个数!
然后每次迭代都会更新一次起始端点st,反复运用本算法。
一定要仔细看视频讲解!!!

#include<iostream>
#include<algorithm>
#define N 100010
#define INF 2e9
using namespace std;
int n ;
struct Range{int l, r;bool operator<(const Range& r1){return l < r1.l;}
}range[N];
int main(){int st , ed;cin >> st >> ed;cin >> n;for(int i = 0 ; i < n ; ++ i){int l , r ;cin >> l >> r;range[i] = {l ,r};} sort(range,range + n);int res = 0 ;bool success = false;for(int i = 0 ; i < n ; ++ i){int j = i ,r = -2e9;while(j < n && range[j].l <= st){r = max(r , range[j].r);++ j;}if(r < st){res = -1;//如果挑出来的最大右端点小于起始端点,那么无解,返回-1break;}++res;if(r >= ed){//如果右边界已经可以超过末尾端点ed,那么求解完毕,返回ressuccess = true;break;}st = r;i = j - 1;}if (!success) res = -1;printf("%d\n", res);
}

相关文章:

AcWing907. 区间覆盖

参考的视频讲解&#xff1a;↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【贪心算法08-区间问题03-区间覆盖】 每次贪心就是选择左端点里面&#xff1c;起始端点里面右边界最大的&#xff0c;这样就是保证了最少区间个数! 然后每次迭代都会更新一次起始端点st&#xff0c;反复运用本算法…...

Unity TMP (TextMeshPro) 更新中文字符集

TMP更新中文字符集 1 字符集缺失说明2 字体的字符表2.1 字符表更新模式&#xff1a;动态2.2 字符表更新模式&#xff1a;静态 3 更新字符集步骤3.1 打开纹理更新面板3.1 导入文本文件3.3 关于警告处理 4 修改TMP默认字体设置 1 字符集缺失说明 使用TMP显示中文需要用到中文字体…...

Leetcode3259. 超级饮料的最大强化能量

Every day a Leetcode 题目来源&#xff1a;3259. 超级饮料的最大强化能量 解法1&#xff1a;记忆化搜索 本题的状态定义 dfs(i,j)。其中 j0,1&#xff0c;分别表示最后选的是 energyDrinkA[i] 还是 energyDrinkB[i]。 为方便实现&#xff0c;把 energyDrinkA 和 energyDri…...

Java题集(由入门到精通)03

此系列文章收录大量Java经典代码题&#xff08;也可以算是leetcode刷题指南&#xff09;&#xff0c;希望可以与大家一起努力学好Java。3、2、1&#xff0c;请看&#xff01; 目录 1.创建学生成绩表 2.冒泡排序 3.模拟彩票中奖 4.杨辉三角 1.创建学生成绩表 输入n个学生的…...

zblog自动生成文章插件(百度AI写作配图,图文并茂)

最近工作比较忙&#xff0c;导致自己的几个网站都无法手动更新&#xff0c;于是乎也想偷个懒把&#xff0c;让AI帮忙打理下自己的网站。我接触chatgpt等AI工具还是比较早了&#xff0c;从openai推出gpt3.5就一直在用&#xff0c;说实话&#xff0c;开始的时候用AI自动更新网站还…...

华为 HCIP-Datacom H12-821 题库 (4)

有需要题库的可以看主页置顶 V群仅进行学习交流 1.缺省情况下&#xff0c;广播型网络中运行 IS-IS 的路由器&#xff0c;DIS 发送 CSNP报文的周期为多少秒&#xff1f; A、10 B、3.3 C、30 D、40 答案&#xff1a;A 解析&#xff1a; 广播型网络中运行 IS-IS 的路由器&am…...

使用seq_file

在《使用procfs》一文的源码示例中有说到proc文件系统每次读取的数据只能是1个页,如果超过则需多次读取,这样的话会增加读取次数,增多系统调用次数,影响了整体的效率,故而才有seq file序列文件的出现,该项功能使得内核对于大文件的读取更加容易。 对于seq file,其结构…...

期货赫兹量化-种群优化算法:进化策略,(μ,λ)-ES 和 (μ+λ)-ES

进化策略&#xff08;Evolution Strategies, ES&#xff09;是一种启发式算法&#xff0c;旨在模仿自然选择的过程来解决复杂的优化问题&#xff0c;尤其在没有显式解、或搜索空间巨大的情况下表现良好。基于自然界的进化原理&#xff0c;进化策略通过突变、选择等遗传算子迭代…...

pytest实战演练

pytest实战演练 pycharm常见操作 创建项目使用虚拟环境 创建文件夹的时候建议使用的创建方式 这样创建是因为python3.0版本之后导包无区别&#xff0c;之前版本导包会报错的 _init_.py文件中建议为空不写内容 _all_[]的含义 是将列表中的方法或变量或类暴漏出去便于使用的生效…...

7、关于LoFTR

7、关于LoFTR LoFTR论文链接&#xff1a;LoFTR LoFTR的提出&#xff0c;是将Transformer模型的注意力机制在特征匹配方向的应用&#xff0c;Transformer的提取特征的机制&#xff0c;在自身进行&#xff0c;本文提出可以的两张图像之间进行特征计算&#xff0c;非常适合进行特…...

硬件工程师笔试面试知识器件篇——电感

目录​​​​​​​ 3、电感 3.1、基础 电感原理图 电感实物图 3.1.1、定义与单位 1)定义: 2) 单位: 3.1.2、物理原理 1)法拉第电磁感应定律: 2)楞次定律: 3.1.3、电感器的构造 3.1.4、类型 3.1.5、应用 3.1.6、特性 3.1.7、设计考虑 3.2、相关问题 3.…...

代码随想录八股训练营第三十六天| C++

前言 一、push_back()和emplace_back()的区别&#xff1f; 1.1.push_back(): 1.2.emplace_back(): 1.3.区别总结&#xff1a; 1.4.使用场景: 二、map dequeu list 的实现原理&#xff1f; 2.1.std::map: 2.2. std::deque: 2.3. std::list: 2.4. 区别总结: 总结 前言…...

学习计算机网络

a类0~127&#xff0c;b类128~191&#xff0c;c类192~223 网络地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff0c;后面是主机位&#xff0c;主机位全部为0&#xff0c;网络地址。 直接广播地址&#xff1a;看子网掩码&#xff0c;分网络位和主机位&#xff…...

Django发送邮件

【图书介绍】《Django 5企业级Web应用开发实战&#xff08;视频教学版&#xff09;》_django 5企业级web应用开发实战(视频教学版)-CSDN博客 Django 5框架Web应用开发_夏天又到了的博客-CSDN博客 本文学习怎么使用Django发送邮件。 尽管使用Python的smtplib模块发送电子邮件…...

T7:咖啡豆识别

T7&#xff1a;咖啡豆识别 **一、前期工作**1.设置GPU,导入库2.导入数据3.查看数据 **二、数据预处理**1.加载数据2.可视化数据3.配置数据集 **三、构建CNN网络模型**1、手动搭建2、直接调用官方模型 **四、编译模型****五、训练模型****六、模型评估****七、预测**八、暂时总结…...

【MATLAB】FIR滤波器的MATLAB实现

FIR滤波器的MATLAB实现 FIR滤波器的设计fir1函数fir2函数 与IIR滤波器相比&#xff0c;FIR滤波器既有其优势也有其局限性。FIR滤波器的主要优点包括&#xff1a; 精确的线性相位响应&#xff1b;永远保持稳定性&#xff1b;设计方法通常是线性的&#xff1b;在硬件实现中具有更…...

【RabbitMQ之一:windows环境下安装RabbitMQ】

目录 一、下载并安装Erlang1、下载Erlang2、安装Erlang3、配置环境变量4、验证erlang是否安装成功 二、下载并安装RabbitMQ1、下载RabbitMQ2、安装RabbitMQ3、配置环境变量4、验证RabbitMQ是否安装成功5、启动RabbitMQ服务&#xff08;安装后服务默认自启动&#xff09; 三、安…...

ISO26262和Aspice之间的关联

ASPICE 介绍&#xff1a; ASPICE&#xff08;Automotive Software Process Improvement and Capability dEtermination&#xff09;是汽车软件过程改进及能力评定的模型&#xff0c;它侧重于汽车软件的开发过程。ASPICE 定义了一系列的过程和活动&#xff0c;包括需求管理、软…...

对极约束及其性质 —— 公式详细推导

Title: 对极约束及其性质 —— 公式详细推导 文章目录 前言1. 对极约束 (Epipolar Constraint)2. 坐标转换 (Coordinate Transformations)3. 像素坐标 (Pixel Coordinates)4. 像素坐标转换 (Transformations of Pixel Coordinates)5. 本质矩阵 (Essential Matrix)6. 线坐标 (Co…...

【论文精读】SCINet-基于降采样和交互学习的时序卷积模型

《SCINet: Time Series Modeling and Forecasting with Sample Convolution and Interaction》的作者团队来自香港中文大学,发表在NeurIPS 2022会议上。 动机 该论文的出发点是观察到时间序列数据具有独特的属性:即使在将时间序列下采样成两个子序列后,时间关系(例如数据…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...