#include<bits/stdc++.h> #include<vector> #include<string> #include<queue> using namespace std; typedef long long ll; const ll N=1e8+5; ll n,m; int a[100005]; int q[100005]; int main(){ }

拿到题目看一下，大体思路还是比较清晰的，用一个数组来装所有的收集到的赠票。每当坐地铁的时候，就直接花钱，然后获得一张赠票，放到数组里面。每当坐公交的时候，看看数组里面有没有时间合适，价格小于现在公交票价的赠票，并且没用过的赠票，直接用时间最早的那一张就可以了。 每张赠票要存三个信息，因此用一个结构体来存。数据不超过10^5 ，因此开一个10^5 长度的数组。 我们想想极限情况什么样子，极限数据10^5 ，假设开始的时候全坐地铁，坐了5∗10^4 次以后，我们的盒子里面有好多票啊。后面全坐公交，要坐5∗10^4 次，每次都在这个大盒子里面找合适的票，复杂度O(n^2 ),总计算量2.5∗10^9。 怎么优化呢?关键点在于题中说每次坐车开始时间都不重合，而且45分钟票就过期。所以理论上来讲，盒子里最多也就有45张没过期的票。大量的票都是已经过期了的，没必要从头扫一遍数组，在大量过期的票中浪费宝贵的青春。所以我们想到类似手写队列的方法，定义一个head变量和一个tail变量，分别表示目前还没过期的第一张票的位置，和下一张新的赠票在数组里要插入的位置，每次从head到小于tail循环即可。每次最多循环45次，总共10^5 次循环，肯定不会超时。

#include<cstdio> using namespace std; typedef int I; struct zxc{ I t,p; bool used=false; }a[100005]; I main(){ I n,ans=0,l=0;scanf("%d",&n); for(I g,p,t,k;n--;){scanf("%d%d%d",&g,&p,&t); if(!g)ans+=p,a[++l].t=t,a[l].p=p; else{k=0; for(I i=l;i&&t-a[i].t<46;i--) if(!a[i].used&&a[i].p>=p)k=i; !k?ans+=p:a[k].used=true; } }printf("%d",ans); }

代码: 下面这个这一个TLE了,勿抄( 我 是 真 的 菜 ) 然后我突然发现了一件事情，才意识我其实没必要所有优惠券都存着…… 我真傻 然后我就做了点优化 A FEW MOMENTS LATER…… 就AC了 我是真的菜 （^ _ ^）V 欢迎加入团队

短小精悍

解题思路： 1. 数据读取与存储： * 从输入中读取乘车记录的数量 n。 * 对于每一条乘车记录，读取交通工具类型（0 代表地铁，1 代表公交车）、票价 price 和乘车时间 t。 * 使用一个结构体数组 s 来存储每次乘坐地铁时获得的优惠票信息，包括优惠票是否可用（flag）、获得优惠票的时间（time）以及乘坐地铁的票价（price）。 2. 处理乘坐地铁的情况： * 当交通工具类型为 0（地铁）时，在结构体数组 s 中新增一条记录，设置 flag 为 true 表示该优惠票可用，记录当前时间 t 作为获得优惠票的时间，同时记录地铁票价 price。 * 将乘坐地铁的票价累加到总花费 sum 中。 3. 处理乘坐公交车的情况： * 当交通工具类型为 1（公交车）时，遍历结构体数组 s 中已有的优惠票记录。 * 对于每一条优惠票记录，如果该优惠票可用（flag 为 true），且当前公交车的乘车时间 t 与获得优惠票的时间 time 之差小于等于 45 分钟，并且公交车的票价 price 不超过获得优惠票时乘坐地铁的票价。满足这些条件时，将该优惠票的 flag 设置为 false 表示已使用。 * 如果遍历完所有优惠票后，没有找到可用的优惠票（即 check 为 true），则将公交车的票价累加到总花费 sum 中。 4. 输出结果： * 最后，输出总花费 sum，即小轩出行的总花费。 题解

#include<bits/stdc++.h> #include<vector> #include<string> #include<queue> using namespace std; typedef long long ll; const ll N=1e8+5; ll n,m; int a[100005]; int q[100005]; int main(){ cin>>n; int ans=0; int r=0; int l=0; for(int i=0;i<n;i++){ int b,c,d; cin>>b>>c>>d; if(b==0){ a[r]=c; q[r]=d; r++; ans+=c; }else{ while(l<r&&d-q[l]>45){ l++; } int flag=1; for(int i=l;i<r;i++){ if(a[i]&&a[i]>=c){ flag=0; a[i]=0; break; } } if(flag) ans+=c; } } cout<<ans<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N=1e5; int a[N]; int q[N]; int l,r; int ans; int n; int ti; int main(){ cin>>n; for(int i=0;i<n;i++){ int num,p,t; cin>>num>>p>>t; if(num0){ a[r]=p; q[r]=t; r++; ans+=p; } if(num1){ while(l<r && abs(t-q[l])>45){ l++; } int cnt=1; for(int j=l;j<r;j++){ if(a[j]&& a[j]>=p){ cnt=0; a[j]=0; break; } } if(cnt==1) ans+=p; } } cout<<ans; return 0; }

#include<bits/stdc++.h> #include<vector> #include<string> #include<queue> using namespace std; typedef long long ll; const ll N=1e8+5; ll n,m; int a[100005]; int q[100005]; int main(){ cin>>n; int ans=0; int r=0; int l=0; for(int i=0;i<n;i++){ int b,c,d; cin>>b>>c>>d; if(b==0){ a[r]=c; q[r]=d; r++; ans+=c; }else{ while(l<r&&d-q[l]>45){ l++; } int flag=1; for(int i=l;i<r;i++){ if(a[i]&&a[i]>=c){ flag=0; a[i]=0; break; } } if(flag) ans+=c; } } cout<<ans<<endl; return 0; }

#include<bits/stdc++.h> #include<vector> #include<string> #include<queue> using namespace std; typedef long long ll; const ll N=1e8+5; ll n,m; int a[100005]; int q[100005]; int main(){ cin>>n; int ans=0; int r=0; int l=0; for(int i=0;i<n;i++){ int b,c,d; cin>>b>>c>>d; if(b==0){ a[r]=c; q[r]=d; r++; ans+=c; }else{ while(l<r&&d-q[l]>45){ l++; } int flag=1; for(int i=l;i<r;i++){ if(a[i]&&a[i]>=c){ flag=0; a[i]=0; break; } } if(flag) ans+=c; } } cout<<ans<<endl; return 0; }