公交换乘

题目 公交换乘

思路分析

直接模拟

做地铁一定要给钱

做公交不一定要给钱

如果在前45分钟内做过地铁 且价格高于本次公交费 且没用过 就可以优惠券抵消

那么就可以把每次做地铁得到的优惠券记录下来

用一个窗口（队列）维护 超过45分钟的就丢弃 出队

那么就只要对每次做公交判断能不能用优惠券抵消（窗口中找 价格高于 且没用过的）

能用就不累加这次的费用 不能用就累加

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

struct Ticket{

    int time;

    int price;

    bool used;

}tk[N];

int n;

int main()

{

    cin>>n;

    int cost=0;

    for(int i=0,l=0,r=0;i<n;i++){

        int type,price,time;

        cin>>type>>price>>time;

        if(type==0){

            cost+=price;

            tk[r++]={time,price,false};

        }

        else{

            while(l<r && time-tk[l].time>45)

                l++;

            bool free=false;

            for(int i=l;i<r;i++){

                if(tk[i].used==false && tk[i].price>=price){

                    tk[i].used=true;

                    free=true;

                    break;

                }

            }

            if(!free)

                cost+=price;

        }

    }

    cout<<cost<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ time needed to buy tickets 🏠 00-刷题理模型 ➡️ 品种临近