---
title: "公交换乘"
created: 2025-11-28
tags:
  - 算法
---

# 公交换乘

## 题目 [公交换乘](https://www.acwing.com/problem/content/description/1164/)

![[image-ce1ccdb6.png]]

## 思路分析

直接模拟

做地铁一定要给钱

做公交不一定要给钱

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

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

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

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

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

## 代码实现

```cpp
#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|time needed to buy tickets]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/队列/品种临近|品种临近]]