【NOIP2019普及组复赛】题2:公交换乘

2024-06-03 13:20

本文主要是介绍【NOIP2019普及组复赛】题2:公交换乘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题2:公交换乘

【题目描述】

著名旅游城市 B B B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案:

1、在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟,即:

t b u s − t s u b w a y ≤ 45 tbus−tsubway≤45 tbustsubway45

2、搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。

3、搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满足条件,则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?

【输入文件】

第一行包含一个正整数 n n n,代表乘车记录的数量。

接下来的 n n n 行,每行包含 3 个整数,相邻两数之间以一个空格分隔。第 i i i 行的第 1 个整数代表第 i i i 条记录乘坐的交通工具,0 代表地铁,1 代表公交车;第 2 个整数代表第 i i i 条记录乘车的票价 p r i c e i price_i pricei ;第三个整数代表第 i i i 条记录开始乘车的时间 t i t_i ti(距 0 时刻的分钟数)。

我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现在同一分钟。

【输出文件】

只有一行,包含一个正整数,代表小轩出行的总花费。

【输入样例1】

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

【输出样例1】

36

【样例1说明】

第一条记录,在第 3 分钟花费 10 元乘坐地铁。

第二条记录,在第 46 分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优惠票,因此没有花费。

第三条记录,在第 50 分种花费 12 元乘坐地铁。

第四条记录,在第 96 分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过 45分钟,所以优惠票已失效,花费 3 元乘坐公交车。

第五条记录,在第 110 分钟花费 5 元乘坐地铁。

第六条记录,在第 135 分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效,而本次公交车的票价为 6 元,高于第五条记录中地铁的票价 5 元,所以不能使用优惠票,花费 6 元乘坐公交车。

总共花费 36 元。

【输入样例2】

6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68

【输出样例2】

32

【样例2说明】

第一条记录,在第 1 分钟花费 5 元乘坐地铁。

第二条记录,在第 16 分钟花费 20 元乘坐地铁。

第三条记录,在第 23 分钟花费 7 元乘坐地铁。

第四条记录,在第 31 分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录,在第 38 分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。

第六条记录,在第 68 分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。

总共花费 32 元。

【数据规模】

对于 30 % 30\% 30% 的数据, n ≤ 1 , 000 , t i ≤ 1 0 6 n≤1,000,t_i≤10^6 n1,000ti106

另有 15 % 15\% 15% 的数据, t i ≤ 1 0 7 , p r i c e i t_i≤10^7,price_i ti107pricei 都相等。

另有 15 % 15\% 15% 的数据, t i ≤ 1 0 9 , p r i c e i t_i≤10^9,price_i ti109pricei 都相等。

对于 100 % 100\% 100% 的数据, n ≤ 1 0 5 , t i ≤ 1 0 9 , 1 ≤ p r i c e i ≤ 1 , 000 n≤10^5,t_i≤10^9,1≤price_i≤1,000 n105ti1091pricei1,000

【代码如下】:

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, s, ans, ynn;
int b[100001], t[100001], p[100001];
int tf[100001][48], youhui[100001], shiyong[100001];
int main() {scanf("%d", &n);for (i = 1; i <= n; i++) scanf("%d%d%d", &b[i], &p[i], &t[i]);for (i = 1; i <= n; i++) {if (b[i] == 0) { ans += p[i]; j = i + 1;while (t[j] - t[i] <= 45 && j <= n) {if (b[j] == 1) {youhui[j]++;tf[j][youhui[j]] = i; }j++;}}}for (i = 1; i <= n; i++)if (b[i] == 1) {ynn = 1; for (j = 1; j <= youhui[i]; j++) {if ((!shiyong[tf[i][j]]) && p[tf[i][j]] >= p[i] && (ynn)) {shiyong[tf[i][j]] = 1;ynn = 0;}}if (ynn) ans += p[i];}cout << ans << endl;return 0; 
}

这篇关于【NOIP2019普及组复赛】题2:公交换乘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1027105

相关文章

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

百度之星 2015 复赛 1001 (数长方形)

数长方形    Accepts: 595    Submissions: 1225  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形

CSP-J/S 复赛程序提交指南,提交错误必爆零!!!

CSP-J/S 复赛题目程序需要以文件的形式提交,如果之前没有了解过,那肯定会爆0,该怎么操作呢? 大家好,我是大李。 针对复赛考试提交详情,这里做个详细介绍,分为文件的创建和文件体提交等事项。 一、关于文件建立 复赛考试时需要根据提示,在桌面建立文件夹,将含有文件体的cpp文件保存至桌面。 每一题的命名都需要根据提示来去命名。 以2023年CSP-J/S 第二轮为例 在电

信息学奥赛初赛天天练-83-NOIP2014普及组-基础题2-输入设备、输出设备、操作系统、二进制、整数除法、while、do while循环

1 NOIP 2014 普及组 基础题2 4 以下哪一种设备属于输出设备( ) A 扫描仪 B 键盘 C 鼠标 D 打印机 5 下列对操作系统功能的描述最为完整的是( ) A 负责外设与主机之间的信息交换 B 负责诊断机器的故障 C 控制和管理计算机系统的各种硬件和软件资源的使用 D 将没有程序编译成目标程序 11 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( ) A 296

免费SSL证书大全,加速普及网站实现HTTPS加密

免费SSL证书大全,加速普及网站实现HTTPS加密   SSL 证书用于加密 HTTP 协议,实现网站通过HTTPS加密协议访问。随着国内外各大网站实现全站 HTTPS 协议,以及搜索引擎对使用 HTTPS 协议网站的更加友好,加之互联网对数据和隐私安全的加强,网站添加 SSL 证书并实现 HTTPS 加密协议访问已经成为趋势和必然。 SSL证书大全​zzzjtd.com 而对于给网站添加

讨论运维监控工具的普及程度

在讨论运维监控工具的普及程度时,加入PIGOSS BSM产品的分析是非常有意义的,因为PIGOSS BSM是一款在中国市场具有一定影响力的运维监控工具。 PIGOSS BSM运维监控工具是一款综合性的IT运维监控解决方案,它能够对多层次的IT资源进行监测,包括但不限于性能监测、事件管理、报表管理等功能模块。PIGOSS BSM的一个独特之处在于其拓扑关联配置工具,这使得用户可以根据自身的I

P2239 [NOIP2014 普及组] 螺旋矩阵

P2239 [NOIP2014 普及组] 螺旋矩阵 50分 //O(n^2)复杂度,能算n<=10000的 #include <bits/stdc++.h>using namespace std;//row当前行, column当前列, left:左边界,righ:右边界,top:上边界,bottom:下边界 int n, x, y, ans, row=1, column=0, lef,

信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点

NOIP 2015 普及组 基础题5 21 重新排列 1234使得每一个数字都不在原来的位置上,一共有( )种排法 22 一棵结点数为 2015的二叉树最多有( )个叶子结点 2 相关知识点 1) 错位排列 考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n) 错排问题最早被尼古拉·伯努利和欧拉研究

信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度

NOIP 2015 普及组 基础题4 11 下面哪种软件不属于即时通信软件( ) A QQ B MSN C 微信 D P2P 16 前序遍历序列与中序遍历序列相同的二叉树为( ) A 根结点无左子树 B 根结点无右子树 C 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D 只有根结点的二叉树或非叶子结点只有右子树的二叉树 18 下列选项中不属于视频文件格式的是( ) A TXT B AV

金融知识普及月答题活动

金融知识普及月答题活动 关键词:金融安全、风险防范、金融常识、反诈宣传 推荐功能:答题、倡议书 宣传角度: 1. 普及金融知识:讲解货币、信用、利率、汇率等基本金融概念,以及储蓄、贷款、信用卡、保险等常见金融产品的特点和使用方法。 2. 防范金融诈骗:揭露各种金融诈骗手段,如电信诈骗、网络诈骗、非法集资等,提高消费者的防范意识和识别能力。 推荐宣传方式: 1. 答题互动:通过在线答题