D - 1D Country(AtCoder Beginner Contest 371)
题目链接:
D - 1D Country (atcoder.jp)
题目描述:
数据范围:
输入输出:
题目分析:
典型的l, r 区间问题,即是前缀和问题,但是注意到数据范围, 数据范围1e-9 到 1e9 数据范围,要是从最小到最大直接for循环去模拟的话,时间复杂度太高了O(2e9),注意到极限总共才2e5个居民,要去想到映射,不在关心他们的位置,而去把下标转换为从1开始的,然后在询问l, r这段区间的时候二分去查到对应的l, r他们映射后的位置,然后用前缀和公式sum[映射后的r] - sum[映射后的l - 1]就是最后的答案,但是我用map去写的时候卡到了最后一个数据,但是用数组就过掉了,why?
最后一个数据没过的代码:
#include<bits/stdc++.h>
#define int long long using namespace std;const int N = 2e5 + 10;map<int, int>mp, ren, sum;
//map<int, int>ren;
int a[N];signed main() {int n, m;cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> a[i];}for(int i = 1; i <= n; i ++ ) {int x;cin >> x;mp[a[i]] += x;}
// sort(a + 1, a + n + 1);//a[0] = 0;
// sum[a[1] - 1] = 0;sum[a[1]] = mp[a[1]];for(int i = 2; i <= n; i ++ ) {sum[a[i]] = sum[a[i - 1]] + mp[a[i]]; }
// for(int i = 1; i <= n; i ++ ) {
// cout << "a[i] = " << a[i] << " sum = " << sum[a[i]] << endl;
// }cin >> m;// 二分的是位置 while(m -- ) {int l, r;cin >> l >> r;// 二分第一个大于等于l的位置int ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] < l) ll = mid;else rr = mid;}int st = ll + 1;// cout << "st = " << st << endl;// 二分最后一个小于等于r的位置 ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] <= r)ll = mid;else rr = mid;}int en = ll;if(r > a[n]) {en = n;}if(l < a[1]) {st = 1;}
// cout << "st - 1 = " << st - 1 << endl;
// cout << "a[st - 1] = " << a[st - 1] << endl;
// cout << "en = " << en << endl;
// cout << "sumEnd = " << sum[a[en]] << endl;
// cout << "sumStart = " << sum[a[st - 1]] << endl;if(st == 1) {cout << sum[a[en]] << endl;} else {cout << sum[a[en]] - sum[a[st - 1]] << endl;}}return 0;
}
/*
7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
1
-10 -4*/
运行结果:
正确代码:
#include<bits/stdc++.h>
#define int long long using namespace std;const int N = 2e5 + 10;int a[N], sum[N];signed main() {int n, m;cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> a[i];}for(int i = 1; i <= n; i ++ ) {int x;cin >> x;sum[i] = sum[i - 1] + x;}cin >> m;// 二分的是位置 while(m -- ) {int l, r;cin >> l >> r;// 二分第一个大于等于l的位置int ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] < l) ll = mid;else rr = mid;}int st = ll + 1;// cout << "st = " << st << endl;// 二分最后一个小于等于r的位置 ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] <= r)ll = mid;else rr = mid;}int en = ll;cout << sum[en] - sum[st - 1] << endl; }return 0;
}
运行结果:
相关文章:

D - 1D Country(AtCoder Beginner Contest 371)
题目链接: D - 1D Country (atcoder.jp) 题目描述: 数据范围: 输入输出: 题目分析: 典型的l, r 区间问题,即是前缀和问题,但是注意到数据范围, 数据范围1e-9 到 1e9 数据范围,要是从最小到最大直接for循环去模拟的话,时间复杂度…...

怎么很多张图片拼接成一张?试试这几种图片拼接方法!
怎么很多张图片拼接成一张?在繁忙的现代生活中,我们不断地捕捉和累积着各式各样的图像,它们如同记忆的珍珠,串联起生活的每一个瞬间,然而,随图片数量的激增,管理它们成为了一项挑战,…...
Python实现优化的分水岭算法
目录 优化分水岭算法的博客1. 分水岭算法优化概述2. 优化分水岭算法的步骤3. Python实现优化后的分水岭算法4. 实例:优化分水岭算法在图像分割中的应用5. 总结 优化分水岭算法的博客 分水岭算法是一种强大的图像分割方法,特别适用于分离不同的对象和区域…...

智慧交通基于yolov8的行人车辆检测计数系统python源码+onnx模型+精美GUI界面
【算法介绍】 智慧交通中,基于YOLOv8的行人车辆检测计数系统是一项高效、准确的技术解决方案。该系统利用YOLOv8这一先进的目标检测算法,结合深度学习技术,能够实时检测并准确计数道路上的行人和车辆。YOLOv8在保证检测速度的同时࿰…...

Linux开发工具的使用
文章目录 vim的使用基本模式介绍光标当前行操作(命令行模式)光标快速定位(命令行模式):插入模式的三种方式(命令行模式):vim基本操作(命令行模式)底行模式的操…...

【devops】devops-git之介绍以及日常使用
本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》:python零基础入门学习 《python运维脚本》: python运维脚本实践 《shell》:shell学习 《terraform》持续更新中:terraform_Aws学习零基础入门到最佳实战 《k8…...
012复杂度07leetcode
视频地址:012复杂度07leetcode_哔哩哔哩_bilibili 网站叫做leetcode。那Linux我相信很多同学都听过这个网站,那这个网站干嘛用呢?这个网站是用于练习算法的一个好网站,那我们这个课程在讲解知识点过程中也会不断的去用到这个网站,…...
4.网络编程
1、目的 传播交流信息TCP:打电话UDP:发短信 2、通信协议: httpTCP/IP簇:三次握手(aba),四次挥手(abba)https 3、IP与端口 1.IP地址类:InetAddress、InetSocketAddress InetAdd…...

OpenCV GUI常用函数详解
在OpenCV的High_level GUI模组中有很多GUI函数,下面介绍几个常用的函数。 图像显示窗口相关函数 生成图像显示窗口函数nameWindow() nameWindow()函数的原型如下: 函数用以创建一个给定名的图像显示窗口(后面简单叫做图像窗口)…...

Tuxera NTFS for Mac破解版下载 Tuxera NTFS for Mac2023激活码 mac电脑ntfs磁盘软件
Tuxera NTFS for Mac是一款优秀的Mac系统完全读写软件,提供Fat32、NTFS、Exfat、mac os扩展格式的转换,稳定性好,传输速度极快。Tuxera NTFS for Mac功能丰富,能修复NTFS卷、创建NTFS磁盘映像、创建NTFS分区等等。同时软件支持所有…...
oceanbase(ob)基于备份集搭建备租户方式
一、搭建备租户方式(基于备份的方式) 注意事项:要有一个源端OB集群和目标端OB集群。 1、新建主租户(如果原来有主租户可是省略) #创建unit create resource unit ut_2c2g max_cpu2, memory_size2G, max_iops10000,l…...

Javase复习day21算法、arrays、Lamdba表达式
常见算法 查找算法 基本查找 package search;public class BasicSearchDemo1 {public static void main(String[] args) {//基本算法(顺序查找)int[] arr {131,23,57,37,95,48,57,43};System.out.println(basicSearch(arr, 43));}public static boo…...

移动硬盘无法读取?别慌!这些方法助你恢复数据!
在我们的日常工作和生活中,移动硬盘作为重要的数据存储工具,承载着珍贵资料。然而,移动硬盘无法被电脑读取的情况时有发生,令人焦急。别慌,下面为大家详细介绍恢复移动硬盘数据的有效方法。 一、检查硬件连接和驱动问题…...
Java集合面试(上)
Java集合面试(上) 集合概述 Java 集合,也叫作容器,主要是由两大接口派生而来:一个是 Collection接口,主要用于存放单一元素;另一个是 Map 接口,主要用于存放键值对 说说List,Set,Queue&#…...

Python画笔案例-046 绘制小红伞
1、绘制小红伞 通过 python 的turtle 库绘制 小红伞,如下图: 2、实现代码 绘制 小红伞,以下为实现代码: """小红伞.py """ import turtledef draw_pattern():"""画填充圆弧"&…...
使用 .NET 6 构建跨平台 Worker Service 服务:跨越平台的 C# 服务开发——解决Windows服务跨平台问题
现代软件开发中,构建跨平台的应用程序变得愈加重要。C# 和 .NET 6 的出现使得在 Windows、Linux 和 macOS 上创建背景服务变得简单而高效。在本指南中,我们将通过创建一个使用 .NET 6 的 Worker Service 来展示如何实现跨平台后台服务。 项目概述 我们…...

terminator-gnome
gnome import os#启动节点指令变量 stere"ros2 launch stereo_c start.py" utils"ros2 launch task utils.launch.py" #tab标题 stere_title"stere_driver" utils_title"utils"#一个终端界面打开5个tab cmd1f"gnome-terminal --…...
7.测试用例设计方法 + Bug
一、正交实验法 1.使用场景 因果关系比较庞大的情况下,不太适合用因果图判定表,在这种情况下,一般会采用正交实验法。 2.例子: 字符属性设置(4个条件) 字体很多 字符样式很多 …...

uniapp小程序,使用腾讯地图获取定位
本篇文章分享一下在实际开发小程序时遇到的需要获取用户当前位置的问题,在小程序开发过程中经常使用到获取定位功能。uniapp官方也提供了相应的API供我们使用。 官网地址:uni.getLocation(OBJECT)) 官网获取位置的详细介绍这里就不再讲述了,大…...
Reactive 编程-Project Reactor
Reactive 编程与 Project Reactor Reactive 编程是一种编程范式,主要用于处理异步数据流。它旨在通过声明式的编程方式处理事件驱动的非阻塞任务,特别适合于构建响应式、可扩展、高并发的应用。随着互联网应用规模的扩大和响应速度的提升需求࿰…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...