CSP 2019 公交换乘
题目来源：牛客网
题目：*
示例1
输入
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
输出
36
题意：
根据输入，计算地铁花费+不能用到优惠券的公交车的花费
知识点：
结构体
思路：
- 题目相对简单：当输入是地铁就直接累计花费，如果是公交，就从前面开始遍历数据，看看是否有满足条件的乘坐地铁后的优惠券，无则累计该公交的花费
- 在储存变量时，可能想到用二维数组储存数据，一行就是出行一次，标记优惠券的情况。但是因为n能达到105，105*3 二维数组空间复杂度比较大（但不至于空间超出限制）。仔细看，其实后面输入的数据，我们只需要考虑前面的地铁的出行的情况，所以可以直接用三个变量储存当前数据（此时用二维数组略微有点浪费），如果是地铁出现，保存到结构体中即可，为了缩短后续遍历时间，结构体的序号为地铁的出现次数即可。
- 设置结构体后，考虑遍历的复杂度，可能能达到n2,而n最大为10 5 ，一定会超时。再想办法缩短时间时，唯一可限定的就是时间间隔<=45min，所以遍历处理公交出行时最多就往前45个位子（如果有，没有就从0开始）。
数据约束：
题目数据相对还好，无约束
参考代码：
#include<bits/stdc++.h>
#define MAX_N 100005
using namespace std;
struct stu{int price;int time;int mark=1;//记录坐地铁后券的使用情况 int s;//标记乘坐的序号
};
stu sub[MAX_N],bus[MAX_N];
int main(){int n,n0=0,num=0;int ty,pr,ti;//n0为地铁数，n1为公交数 cin>>n;for(int i=0;i<n;i++){cin>>ty>>pr>>ti;if(ty==0){ //标记地铁即可 sub[n0].price=pr;sub[n0].time=ti;sub[n0].s=i;n0++;num+=pr; //直接+钱 }else{int j=0,flag=1;n0-45>=0?j=n0-45:j=0;
// cout<<"j: "<<j<<endl;for(j;j<n0;j++){ //价格更小，间隔《=45，是该公交之前的地铁在前， 券没用过 if(pr<=sub[j].price&&ti-sub[j].time<=45&&i>=sub[j].s&& sub[j].mark==1){sub[j].mark=0;flag=0;break;}}if(flag){num+=pr;}}}cout<<num; return 0;
}
