【AcWing】【C++】模板之区间和与区间合并

最近在对程序设计算法进行复习,终于复习完了AcWing基础算法课的第一章,在此对第一章最后两个模板区间和与区间合并进行记录与分享。

区间和

题目描述与输入输出样例

题目来自于AcWing 802. 区间和。
在这里插入图片描述

思路

从题目描述来说,第一眼看来这是一道前缀和的裸题,但是仔细查看题目会发现,题目描述中有提到“无限长的数轴”,并且索引 x x x以及 l l l r r r的值可能为负,因此可能会出现如下情况,即区间范围非常的大,但是在这个非常大的区间当中,只存在两个位置有值,其它位置为全零,并且这两个位置相距非常远。

因此,想要解决这道题目,需要对题目中原始的下标索引进行离散化,这就引出了以下离散化的模板。

首先,使用pair<int, int>数据结构对两种类型的数据进行存储,分别是“在某个位置x加上c”以及“求区间[l, r]之间所有数的和”,分别使用类型为vector<pair<int, int> >addsquery来存储。之后,再使用一个vector<int>类型的alls来存储所有出现过的下标。

然后,我们需要对下标进行排序,使用sort(alls.begin(), alls.end())来快速完成。排序之后,还需要对下标进行一次去重操作,使用alls.erase(unique(alls.begin(), alls.end()), alls.end())来快速完成。至此,便得到了离散化之后的数组下标索引,存储在alls当中。

现在,我们就可以对加法进行操作了,根据上文所描述,adds当中的元素存储了数轴上的相加操作,假设itemadds当中的元素,item.first存储的是离散化前原始下标对应的要执行加法的位置,而item.second存储的是要加的值。需要注意的是,我们需要使用的是离散化之后的下标,而离散化之后的下标被存储在alls当中,alls的下标就是离散化之后的下标,而下标位置的值存储的是离散化之前的索引。并且,alls当中的值是有序的,根据这一性质,我们可以在 O ( n log ⁡ n ) O(n\log n) O(nlogn)内使用二分查找来寻找离散化之前索引在alls当中对应的下标,即离散化之后的下标。将这一二分查找的函数记作findf,使用findf(item.first)即可找到离散化之后要执行加法的位置的索引。

同理,查询操作的 l l l r r r也可以使用上述findf函数找到离散化后的下标。在执行查询操作之前,需要先对离散化后的数组求一遍前缀和,以在 O ( 1 ) O(1) O(1)内执行查询区间和的操作。

完整代码如下:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int maxn = 3e5 + 5;
typedef pair<int, int> PII;vector<PII> adds, query;
vector<int> alls;
int a[maxn] = {0}, s[maxn] = {0};int n, m;int findf(int x) {int l = 0, r = alls.size() - 1;while(l < r) {int mid = (l + r) >> 1;if(alls[mid] >= x)  r = mid;else                l = mid + 1;}return r + 1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for(int i=1; i<=n; i++) {int x, c;cin >> x >> c;adds.push_back({x, c});alls.push_back(x);}for(int i=1; i<=m; i++) {int l, r;cin >> l >> r;query.push_back({l, r});alls.push_back(l);alls.push_back(r);}sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());for(auto & item : adds) {int x = findf(item.first);a[x] += item.second;}for(int i=1; i<=alls.size(); i++) {s[i] = s[i-1] + a[i];}for(auto & item : query) {int l = findf(item.first), r = findf(item.second);cout << s[r] - s[l-1] << endl;}return 0;
}

区间合并

题目描述与输入输出样例

题目来自于AcWing 803. 区间合并。
在这里插入图片描述
这道题目相较于区间和来说简单了很多。

思路

这道题目有两种解法,一种是区间合并模板,一种是对左边界进行排序之后进行贪心。

区间合并模板

区间和并模板的思路非常清晰,同样使用vector<pair<int, int> >来对区间的端点进行存储。之后,直接开始执行区间合并操作。

首先初始化一个vector<pair<int, int> >类型的res作为区间合并的最终结果。声明左右边界l = -2e9, r = -2e9;作为区间端点。

之后,再对存储了输入区间的vector进行排序,按照左端点进行排序。

对存储了区间的vector进行遍历,假设range是其中的一段区间,range.first存储的是区间的左端点,range.second存储的是右端点。首先使用range.firstr进行比较,如果该区间的左端点比[l, r]区间的右端点还要大,说明range区间不能被合并到[l, r]区间当中,令l = range.first, r = range.second,代表对[l, r]区间进行更新。此时,如果l != -2e9,说明[l, r]区间还未被初始化,这时将这个新的区间加入到res当中。

而如果range区间的左端点比[l, r]区间的右端点小,说明这个区间可以被合并到[l, r]区间内,令r = max(r, range.second),意味着如果range包含在[l, r]内,不需要对[l, r]的右端点进行更新,否则更新右端点。

最后,如果l != -2e9,则将当前的[l, r]区间加入到res当中,它的作用有两个,避免n = 0的特殊情况下将l = -2e9, r = -2e9加入到res当中,此外对于n = 1的情况,可以避免[l, r]没有被加入到res当中。

最后输出res的尺寸就是最终答案。

代码如下:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;typedef pair<int, int> PII;
vector<PII> segs;int n;void merge(vector<PII> & segs) {vector<PII> res;sort(segs.begin(), segs.end());int l = -2e9, r = -2e9;for(auto range : segs) {if(range.first > r) {if(l != -2e9)   res.push_back({l, r});l = range.first;r = range.second;}    else {r = max(r, range.second);}}if(l != -2e9)   res.push_back({l, r});segs = res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for(int i=1; i<=n; i++) {int l, r;cin >> l >> r;segs.push_back({l, r});}merge(segs);cout << segs.size();return 0;
}

贪心

贪心的思路其实更好理解,使用贪心不必对合并后的区间进行记录,而直接使用一个整型变量res来对答案进行记录即可,显然使用贪心可以AC这道题,但是不适合学习区间合并的模板以得到完整的合并区间。

贪心的代码如下:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;typedef pair<int, int> PII;
vector<PII> range;int n;
int res = 0;int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for(int i=1; i<=n; i++) {int l, r;cin >> l >> r;range.push_back({l, r});}sort(range.begin(), range.end());int l = -2e9, r = -2e9;for(auto rg : range) {if(rg.first > r) {res ++ ;l = rg.first;r = rg.second;} else {r = max(r, rg.second);}}cout << res;return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Fyne ( go跨平台GUI )中文文档-入门(一)

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法go代码展示为Go 1.16 及更高版本, ide为goland2021.2 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne ( go跨平台GUI )…

镭射限高防外破预警装置-线路防外破可视化监控,安全尽在掌握中

镭射限高防外破预警装置-线路防外破可视化监控&#xff0c;安全尽在掌握中 在城市化浪潮的汹涌推进中&#xff0c;电力如同现代社会的生命之脉&#xff0c;其安全稳定运行直接关系到每一个人的生活质量和社会的整体发展。然而&#xff0c;随着建设的加速&#xff0c;电力设施通…

部署wordpress项目

一、先部署mariadb 二、在远程登录工具上进行登录测试&#xff0c;端口号为30117&#xff0c;用户为 root&#xff0c;密码为123 三、使用测试工具&#xff1a; [rootk8s-master aaa]# kubectl exec -it pods/cluster-test0-58689d5d5d-7c49r -- bash 四、部署wordpress [root…

论文阅读 | 基于流模型和可逆噪声层的鲁棒水印框架(AAAI 2023)

Flow-based Robust Watermarking with Invertible Noise Layer for Black-box DistortionsAAAI, 2023&#xff0c;新加坡国立大学&中国科学技术大学本论文提出一种基于流的鲁棒数字水印框架&#xff0c;该框架采用了可逆噪声层来抵御黑盒失真。 一、问题 基于深度神经网络…

【AI算法岗面试八股面经【超全整理】——NLP】

AI算法岗面试八股面经【超全整理】 概率论【AI算法岗面试八股面经【超全整理】——概率论】信息论【AI算法岗面试八股面经【超全整理】——信息论】机器学习【AI算法岗面试八股面经【超全整理】——机器学习】深度学习【AI算法岗面试八股面经【超全整理】——深度学习】NLP【A…

教师管理系统小程序+ssm论文源码调试讲解

第二章 开发工具及关键技术介绍 2.1 JAVA技术 Java主要采用CORBA技术和安全模型&#xff0c;可以在互联网应用的数据保护。它还提供了对EJB&#xff08;Enterrise JavaBeans&#xff09;的全面支持&#xff0c;java servlet AI&#xff0c;JS&#xff08;java server ages&…

Unity 热更新(HybridCLR+Addressable)-创建Addressable资源

三、创建Addressable资源 创建三个文件夹&#xff0c;放Addressable资源&#xff0c;里面对应放程序集&#xff0c;预制体以及场景 拖拽到Addressable Groups对应组中 其中文件名太长&#xff0c;带着路径&#xff0c;可以简化名字 创建一个脚本&#xff0c;对于这个脚本进行一…

vue3自定义hooks

引言 Vue3引入了组合式API&#xff0c;使得代码逻辑更自由、灵活。其中自定义Hooks能让我们将客服用的逻辑抽离成一个独立的函数&#xff0c;以实现在多个组件中复用的目的。可以简单理解成封装成一个模块&#xff0c;以方便其他地方调用。 实现 自定义hooks useDog impor…

杰发科技——Eclipse环境安装

文件已传到网盘&#xff1a; 1. 安装文件准备 2. 安装Make 默认路径&#xff1a;C:\Program Files (x86)\GnuWin32\bin\ 不复制的话会报错 Error: Program "make" not found in PATH 3. 安装工具链 默认路径&#xff1a;C:\Program Files (x86)\Arm GNU Toolchain…

闯关leetcode——69. Sqrt(x)

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/sqrtx/description/ 内容 Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You mu…

计算机毕业设计之:基于微信小程序的中药材科普系统(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

模拟实现(优先级队列)priority_queue:优先级队列、仿函数、 反向迭代器等的介绍

文章目录 前言一、优先级队列二、仿函数三、 反向迭代器总结 前言 模拟实现&#xff08;优先级队列&#xff09;priority_queue&#xff1a;优先级队列、仿函数、 反向迭代器等的介绍 一、优先级队列 优先级队列本质是一个堆&#xff0c;使用vector容器进一步改进进行实现&am…

vue使用PDF.JS踩的坑--部署到服务器上显示pdf.mjs viewer.mjs找不到资源

之前项目使用的pdf.js 是2.15.349版本&#xff0c;最近换了一个4.6.82的版本&#xff0c;在本地上浏览文件运行的好好的&#xff0c;但是发布到服务器&#xff08;IIS&#xff09;上打不开文件&#xff0c;控制台提示找不到pdf.mjs viewer.mjs。 之前使用的2.15.349pdf和viewer…

mock虚拟接口技术

一、什么是mock mock指的就是使用mock创建出来的一个虚拟的接口 二、对于测试人员而言&#xff0c;我们为什么要使用mock 当我们进行接口测试时&#xff0c;如果对应的接口还没有开发好&#xff0c;但是我们又需要用到这个接口响应的信息&#xff0c;这个时候我们就可以使用…

邮件发送高级功能详解:HTML格式、附件添加与SSL/TLS加密连接

目录 一、邮件HTML格式设置 1.1 HTML邮件的优势 1.2 HTML邮件的编写 二、添加附件 2.1 附件的重要性 2.2 添加附件的代码示例 2.3 注意事项 三、使用SSL/TLS加密连接 3.1 SSL/TLS加密的重要性 3.2 SSL/TLS加密的工作原理 3.3 在邮件发送中启用SSL/TLS 3.3.1 邮件客…

智能算法躲避拥堵,高德企业用车上线“动态选路服务”为出行提效

近日&#xff0c;高德企业用车正式上线了一项全新服务——“动态选路服务”&#xff0c;旨在基于智能算法&#xff0c;动态规避突发拥堵路线&#xff0c;为企业用车用户提供更便捷、智能的出行方案。 以技术着眼细节&#xff0c;高德企业用车在帮助企业用车用户节约出行时间和…

飞睿智能实时雷达活体探测传感器模块,智能家居静止检测实时感知人员有无

随着科技的飞速发展&#xff0c;我们的生活正在经历着未有的创新。在这个创新的浪潮中&#xff0c;实时雷达活体探测传感器模块的技术正逐渐崭露头角&#xff0c;以其独特的优势为我们的生活带来安全与便捷。今天&#xff0c;我们就来详细探讨一下这项技术&#xff0c;看看它是…

TCL25届校招测评笔试TAS人才测评题库:高分攻略真题分析

&#x1f31f; 职场新人必看&#xff1a;TCL校招测评全解析 &#x1f31f; 亲爱的小伙伴们&#xff0c;你是否正准备踏入职场&#xff0c;或是对即将到来的校招感到既兴奋又紧张&#xff1f;今天&#xff0c;我将带你深入了解TCL校招中的TAS人才测评&#xff0c;让你在面试前做…

MyBatis - 动态SQL

前言 我们在某网站填写个人信息时&#xff0c;时常会遇到可以选填的空&#xff08;即可填&#xff0c;可不填&#xff09;&#xff0c;由于之前讲过的Java中的SQL语句都是固定的&#xff0c;且我们不可能对所有情况都写出与之对应的插入语句&#xff08;太过繁琐&#xff09;&…

最新简洁大方的自动发卡网站源码/鲸发卡v11.61系统源码/修复版

源码简介&#xff1a; 最新简洁大方的自动发卡网站源码&#xff0c;它就是鲸发卡v11.61系统源码&#xff0c;它是修复版。 说到鲸发卡系统&#xff0c;鲸发卡系统在发卡圈很多人都知道的&#xff0c;它是市面最好发卡系统之一&#xff0c;操作起来简单得很&#xff0c;界面也…