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

洛谷P5661:公交换乘 ← CSP-J 2019 复赛第2题

【题目来源】
https://www.luogu.com.cn/problem/P5661
https://www.acwing.com/problem/content/1164/

【题目描述】
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案:
1.在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟,即:tbus−tsubway≤45
2.搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车,但每次搭乘公交车只能使用一张优惠券。
3.搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满足条件,则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?

【输入格式】
第一行包含一个正整数 n,代表乘车记录的数量。
接下来的 n 行,每行包含 3 个整数,相邻两数之间以一个空格分隔。第 i 行的第 1 个整数代表第 i 条记录乘坐的交通工具,0 代表地铁,1 代表公交车;第 2 个整数代表第 i 条记录乘车的票价 pricei ;第三个整数代表第 i 条记录开始乘车的时间 ti(距 0 时刻的分钟数)。
我们保证出行记录是按照开始乘车的时间顺序给出的,且 不会有两次乘车记录出现在同一分钟。

【输出格式】
有一行,包含一个正整数,代表小轩出行的总花费。

【数据范围】
对于 30% 的数据,n≤1000,ti≤10^6。
另有 15% 的数据,ti≤10^7,pricei 都相等。
另有 15% 的数据,ti≤10^9,pricei 都相等。
对于 100% 的数据,n≤10^5,ti≤10^9,1≤pricei≤1000。
注意,本题采用官方比赛实际数据,ti 的真实范围为 ti≤10^7,特此声明。


【输入样例】
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

【输出样例】
36

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
struct Ticket {int price, time, used;
}q[N];int head,tail;
int cost;
int n;int main() {cin>>n;for(int i=0; i<n; i++) {int op,price,time;cin>>op>>price>>time;if(op==0) {cost+=price;q[tail].time=time+45;q[tail++].price = price;} else {while(head<tail && q[head].time<time) {head++;}bool found=false;for(int j=head; j<tail; j++) {if(q[j].price>=price && q[j].used==0) {found=true;q[j].used=1;break;}}if(!found) cost+=price;}}cout << cost << endl;return 0;
}/*
in:
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135out:
36
*/



【参考文献】
https://www.luogu.com.cn/problem/solution/P5661



 

相关文章:

洛谷P5661:公交换乘 ← CSP-J 2019 复赛第2题

【题目来源】https://www.luogu.com.cn/problem/P5661https://www.acwing.com/problem/content/1164/【题目描述】 著名旅游城市 B 市为了鼓励大家采用公共交通方式出行&#xff0c;推出了一种地铁换乘公交车的优惠方案&#xff1a; 1.在搭乘一次地铁后可以获得一张优惠票&…...

mysql优化之索引

索引官方定义&#xff1a;索引是帮助mysql高效获取数据的数据结构。 索引的目的在于提高查询效率&#xff0c;可以类比字典。 可以简单理解为&#xff1a;排好序的快速查找数据结构 在数据之外&#xff0c;数据库系统还维护着满足特定查找算法的数据结构&#xff0c;这种数据…...

文件系统详解

目录 文件系统&#xff08;1&#xff09; 第一节文件系统的基本概念 一、文件系统的任务 二、文件的存储介质及存储方式 三、文件的分类 第二节 文件的逻辑结构和物理结构 一、文件的逻辑结构 二、文件的物理结构 文件系统&#xff08;2&#xff09; 第三节 文件目…...

有名管道及其应用

创建FIFO文件 1.通过命令&#xff1a; mkfifo 文件名 2.通过函数: mkfifo #include <sys/types.h> #include <sys/stat.h> int mkfifo(const char *pathname, mode_t mode); 参数&#xff1a; -pathname&#xff1a;管道名称的路径 -mode&#xff1a;文件的权限&a…...

加州大学伯克利分校 计算机科学专业

加州大学伯克利分校 计算机科学专业 cs 61a cs 61b cs61c...

一个关于 i++ 和 ++i 的面试题打趴了所有人

前言 都说大城市现在不好找工作&#xff0c;可小城市却也不好招人。 我们公司招了挺久都没招到&#xff0c;主管感到有些心累。 我提了点建议&#xff0c;是不是面试问的太深了&#xff0c;在这种小城市&#xff0c;能干活就行。 他说自己问的面试题都很浅显&#xff0c;如果答…...

程序员的快乐如此简单

最近在GitHub上发起了一个关于Beego框架的小插件的开源仓库&#xff0c;这一举动虽然看似微小&#xff0c;但其中的快乐和意义却是无法用言语表达的。 Beego是一个开源的Go语言Web框架&#xff0c;它采用了MVC架构模式&#xff0c;并集成了很多常用的功能和中间件。小插件是指…...

浅谈云原生Cloud Native

目录 1.云原生是什么2.云原生与传统软件有什么区别3.云原生有哪些代表性的技术 1.云原生是什么 云原生&#xff08;Cloud Native&#xff09;是一种构建和运行应用程序的方法&#xff0c;可以充分利用云计算模型的优势。云原生是一种面向服务的架构&#xff08;SOA&#xff09…...

解决react报错“JSX 表达式必须具有一个父元素“

现象如下&#xff1a; 原因&#xff1a; 新插入的dom元素跟已有的dom元素平级了&#xff0c;必须创建一个共有的根元素 解决办法&#xff1a; 使用<> </>标签作为根元素&#xff0c;把所有子元素包裹起来 <> ....原代码 </> 问题解决&#xff01;…...

Spring学习笔记7 Bean的生命周期

Spring学习笔记6 Bean的实例化方式_biubiubiu0706的博客-CSDN博客 Spring其实就是一个管理Bean对象的工厂.它负责对象的创建,对象的销毁. 这样我们才可以知道在哪个时间节点上调用了哪个类的哪个方法,知道代码该写在哪里 Bean的生命周期之粗略5步 Bean生命周期的管理可以参考S…...

React 如何导出excel

在现代的Web开发中&#xff0c;数据导出是一个非常常见的需求。而在React应用中&#xff0c;我们经常需要将数据导出为Excel文件&#xff0c;以便用户可以轻松地在本地计算机上查看和编辑。本文将介绍如何在React应用中实现导出Excel文件的功能。 章节一&#xff1a;安装依赖 …...

Texlive2020 for win10 宏包更新

用命令提示符更新texlive的宏包,这个方法非常简单实用 1.以管理员身份打开命令提示符 2.系统自动选择镜像网站 tlmgr option repository ctan 3.更新宏包 tlmgr update --self --all 其中–self参数表示升级tlmgr本身,–all表示升级所有宏包,这样就可以将所有宏包更新了 4.列…...

Ps 在用鼠标滚轮缩放图片时,速度太快?

1.原因 在于安装了第三方鼠标优化软件Mos&#xff0c;它起着对第三方鼠标全局浏览效果的优化&#xff0c;使浏览更加顺滑&#xff0c;而不精确&#xff0c;消除了mac使用第三方鼠标浏览页面时的卡顿问题。这也使得像ps、ai这类软件&#xff0c;在进行页面缩放时&#xff0c;变得…...

基于docker进行Grafana + prometheus实现服务监听

基于docker进行Grafana Prometheus实现服务监听 Grafana安装Prometheus安装Jvm监控配置服务器主机监控(基础cpu&#xff0c;内存&#xff0c;磁盘&#xff0c;网络) Grafana安装 docker pull grafana/grafanamkdir /server/grafanachmod 777 /server/grafanadocker run -d -p…...

模型层及ORM介绍

模型层及ORM介绍 模型层 负责跟数据库之间进行通信 配置MySQL&#xff0c;下载MySQLclient 创建数据库 进入mysql数据库执行create database 数据库名 default charset utf8通常数据库名跟项目名保持一致settings.py里进行数据库的配置修改 DATABASES 配置项的内容&#x…...

QQ邮箱怎么设置SMTP接口服务器?

在现如今信息快速传递的时代&#xff0c;邮件已成为我们工作、学习和生活中必不可少的一部分。而作为每位用户必备的一款邮箱&#xff0c;QQ邮箱一直以其稳定、高效、安全的特点深受大家的青睐。但是你是否觉得每次发邮件都需要打开QQ邮箱网页&#xff0c;进行繁琐的操作很是麻…...

【操作系统笔记四】高速缓存

CPU 高速缓存 存储器的分层结构&#xff1a; 问题&#xff1a;为什么这种存储器层次结构行之有效呢&#xff1f; 衡量 CPU 性能的两个指标&#xff1a; 响应时间&#xff08;或执行时间&#xff09;&#xff1a;执行一条指令平均时间 吞吐量&#xff0c;就是 1 秒内 CPU 可以…...

uniapp获取openid

要获取用户的openid&#xff0c;需要使用微信小程序的登录API。以下是一个简单的示例代码&#xff1a; // 在page中引入wx-login组件 import wxLogin from /components/wx-loginexport default {components: { wxLogin },data() {return {openid: }},methods: {// wxLogin组件…...

测试工程师面试之设计测试用例

以下的问题答案&#xff0c;仅供参考&#xff0c;如小伙伴们有更好的答案&#xff0c;欢迎大家评论区留言&#xff0c;谢谢大家 测试工程师面试之设计测试用例 1、请说一说简单用户界面登陆过程都需要做哪些分析2、 请对此系统设计测试用例&#xff1a;一个系统&#xff0c;多个…...

html页面仿word文档样式(vue页面也适用)

目录 文章title&#xff1a; 标题&#xff1a; 正文&#xff1a; 完整代码&#xff1a; 页面效果&#xff1a; 文章title&#xff1a; <div><h3 style"display: flex;justify-content: center; align-items: center; color: #000;">实验室招新报名公…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...