PDF文档公众号回复关键字:20240924
1 2019 CSP-J 题目2 公交换乘
[题目描述]
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案
在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即： tbus−tsubway≤45
搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车
搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票
现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗?
[输入格式]
输入文件的第一行包含一个正整数 n，代表乘车记录的数量
接下来的 n 行，每行包含 3 个整数，相邻两数之间以一个空格分隔
第 i行的第 1 个整数代表第 i条记录乘坐的交通工具，0 代表地铁，1 代表公交车
第 2 个整数代表第 i条记录乘车的票价 pricei
第三个整数代表第 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
输入 #2
6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68
输出 #2
32
说明/提示
样例 1 说明
第一条记录，在第 3 分钟花费 10 元乘坐地铁。
第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。
第三条记录，在第 50 分钟花费 12 元乘坐地铁。
第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3 元乘坐公交车。
第五条记录，在第 110 分钟花费 5 元乘坐地铁。
第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票，花费 6 元乘坐公交车。
总共花费 36 元。
样例 2 说明
第一条记录，在第 1 分钟花费 5 元乘坐地铁。
第二条记录，在第 16 分钟花费 20 元乘坐地铁。
第三条记录，在第 23 分钟花费 7 元乘坐地铁。
第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。
第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。
总共花费 32 元。
2 相关知识点
结构体
无构造函数
#include<bits/stdc++.h>
using namespace std;
/*
定义结构体 包括2个成员x和y
*/
struct xy{
int x;
int y;
};
int main(){
xy xy1;//声明结构体变量xy1
xy1.x=1;//对成员变量x赋值
xy1.y=2;//对成员变量y赋值
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
构造函数
#include<bits/stdc++.h>
using namespace std;
/*
结构体构造函数体内为成员变量赋值
*/
struct xy{
int x;
int y;
//和结构体名称相同的函数称为构造函数
xy(int _x,int _y){//通过构造函数对成员变量赋值
x=_x;
y=_y;
}
};
int main(){
xy xy1=xy(1,2);//通过构造函数传入参数给成员变量x,y
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
}
初始化列表构造
#include<bits/stdc++.h>
using namespace std;
/*
C++提供了给成员变量初始化并赋值的方式，这就是初始化列表。
在构造函数的()后，{}之前写，格式是冒号+成员名（初始值），
对与自定义类型则是调用它的构造函数初始化
*/
struct xy{
int x;
int y;
xy(int x,int y):x(x),y(y){}//初始化列表方式对成员变量进行初始化
};
int main(){
xy xy1=xy(1,2);//通过构造函数传入参数给成员变量x,y
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
}
集合存在性
判断集合中，即数组，set，map中是否存在某个元素，通常做法为
设置一个布尔变量初始flag=false
循环数组，逐一判断是否有此元素，如果有说明找到设置布尔变量flag=true，并退出循环
判断布尔变量flag确定此元素是否存在
#include<bits/stdc++.h>
using namespace std;
/**
输入a数组的个数
r 要在a中查找的数
a[100]输入一些整数，最多100个
*/
int n,r,a[100];
int main(){
cin>>n>>r;
for(int i=0;i<n;i++){
cin>>a[i];
}
bool flag= false;
for(int i=0;i<n;i++){
if(a[i]==r){
flag=true;
break;
}
}
if(flag){
cout<<"数组a中存在r";
}else{
cout<<"数组a中不存在r";
}
return 0;
}
/**
输入:
10 8
1 2 3 4 5 9 8 7 6 0
输出:
数组a中存在r
*/
3 思路分析
-
地铁票需要计费，累加到计费变量，同时地铁票累加到数组，供坐公交时查
-
坐公交时，在地铁记录数组中从前到后找到未超过45分钟，且地铁票金额>乘坐公交金额
符合上面条件，免票，并且此leij地铁票已经使用，标记后续不再使用，方法是pas[j].price=0;
不符合上面条件，需买票累加到计费变量
#include<bits/stdc++.h>
using namespace std;
struct piao{
int type;
int price;
int time;
};
const int N=1e5+10;
int n,total,idx;
piao pas[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
piao pa;
cin>>pa.type>>pa.price>>pa.time;
if(pa.type==0){//地铁 收费
total+=pa.price;
pas[idx++]=pa;
}else if(pa.type==1){//公交
bool flag=false;
for(int j=0;j<idx;j++){
if(pa.time-pas[j].time<=45 && pa.price<=pas[j].price){//免票
pas[j].price=0;
flag=true;
break;
}
}
if(!flag){//false 未找到需要买票
total+=pa.price;
}
}
}
cout<<total;
return 0;
}
优化版本
优化思路
由于出行记录是按照乘车时间给出的，且两次出行记录不会在同一分钟，因此只要本次地铁票超45分钟，不能使用，下次也不能使用
在每次坐公交时，判断本次和地铁乘坐记录是否超过45分钟，超过则记录从此次地铁记录位置
下次乘坐公交时，从上次记录位置开始，记录位置前面的不再循环判断，减少循环次数
#include<bits/stdc++.h>
using namespace std;
struct piao{
int type;
int price;
int time;
};
const int N=1e5+10;
int n,total,idx,startIdx;
piao pas[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
piao pa;
cin>>pa.type>>pa.price>>pa.time;
if(pa.type==0){//地铁 收费
total+=pa.price;
pas[idx++]=pa;
}else if(pa.type==1){//公交
bool flag=false;
for(int j=startIdx;j<idx;j++){
if(pa.time-pas[j].time<=45){//在时间范围内
if(pa.price<=pas[j].price){//免票
pas[j].price=0;
flag=true;
break;
}
}else{//由于出行记录是按照乘车时间给出的，且两次出行记录不会在同一分钟，因此只要本次地铁票超45分钟，不能使用，下次也不能使用
startIdx=j;
}
}
if(!flag){//false 未找到需要买票 累加买票金额
total+=pa.price;
}
}
}
cout<<total;
return 0;
}