模拟($O(n^2)$ 30pts)

• 依次枚举每张票，如果是地铁直接购买且存下来，否则就判断能否在以前的地铁里面找到一张可以用的。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Node{ 
    int p,t; //票钱，时间
    bool flag; //是否使用
};
int main()
{
    int n;
    cin>>n;
    vector<Node> q;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        if(k==0) //地铁必须给钱
        {
            int p,t;
            cin>>p>>t;
            res+=p;
            q.push_back({p,t,0});
          
        }
        else
        {
            int p,t;
            cin>>p>>t; //获取公交的价格
           
            for(int i=0;i<q.size();i++)
            {
                if(q[i].flag==0&&q[i].p>=p&&t-q[i].t<=45) //找到了一张可以用的
                {
                    q[i].flag=true; //标记地铁票已经用过了
                    p=0; //公交免费
                    break;
                }
            }
            res+=p;
        }
    }
    cout<<res;
    return 0;
}

模拟($O(n)$ 100pts)

• 可以使用队列只储存45分钟以内的有效票

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Node{ 
    int p,t; //票钱，时间
    bool flag; //是否使用
}q[N];
int main()
{
    int n;
    cin>>n;
    int hh=0,tt=-1;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        if(k==0) //地铁必须给钱
        {
            int p,t;
            cin>>p>>t;
            res+=p;
            q[++tt]={p,t,0};
        }
        else
        {
            int p,t;
            cin>>p>>t; //获取公交的价格
            while(hh<=tt&&t-q[hh].t>45) hh++; //删除过期的票
            for(int i=hh;i<=tt;i++)
            {
                if(q[i].flag==0&&q[i].p>=p) //找到了一张可以用的
                {
                    q[i].flag=true; //标记地铁票已经用过了
                    p=0; //公交免费
                    break;
                }
            }
            res+=p;
        }
    }
    cout<<res;
    return 0;
}