搬运一篇我发在 lg 博客的题解：原题解链接。

以下为原题解，写于考后大概一天左右

---

考都考了，那就发一篇吧

（我会把pj前三题的题解做个整合版发在lg博客里，敬请期待！）

这道题基本在意料之中，和龙虎斗类型相似的枚举模拟题，虽然算法简单但是小坑无数

Part 1

看到这题第一反应是“这么简单的一题啊”

迅速开编。

直接模拟即可。开变量记录上一张票的截止时间，逢公交判断即可。

发现可以边读入边处理，节省空间

5min after...

诶肿么样例输错了？！[蒟蒻在线懵逼]

好再来康康...

诶！

由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票

woc...还有这个要求！

Part 2

那好办，直接再开个变量记录上一次地铁票价，加一个判断就成。

3min后...

好，我们来看看第一个样例...啊！输对了！[蒟蒻的笑容]

然后突然扫到一句话：

如果有**多张优惠票**满足条件，则优先消耗获得最早的优惠票。

woc!!还会有多张优惠票?!那...直接开一个变量记录的方法直接推翻。

[来自蒟蒻的尴尬而又不是礼貌的微笑]

Part 3

于是决定开结构体数组存储票价信息。

然后又发现如果每次做公交时都从头遍历一遍所有票会T，所以又愣住了

然后突然想起 P2058 [NOIp2016] 海港的一种“滑动窗口”算法，惊讶的发现可以用于这道题。

于是算法就是**记录下每次可用票的区间[x,y]的x和y，于是循环可以从x至y，就不会T了。**

可用票的区间定义为：全体“未过期”的票包含在此区间内。

有那么一瞬间想到了（在一位奆佬博客里看到过的）单调队列 （此处，原错写为“优先队列”，已更正，可见我有多蒟蒻） ，但是忘了肿么写了。所以就采用了结构体数组加“滑动窗口”。~~蒟蒻太弱了居然没有意识到这就是优先队列~~

于是代码就有了。15:30过了大样例，就默认锕了。

#include<iostream>
using namespace std;
  //【1.建立结构体】
struct Ticket
{
    int price;
    int last;//最晚使用时间
    bool used;//是否已使用
};
Ticket tic[100001];
  //【2.输入部分】
int main() 
{
    bool bus; 
    int t,pri,x=1,y=0;//pri为每次输入的价格，x，y如上所述
    int n,sum=0;//sum记录钱数
    cin>>n;
  //【3.地铁的情况】
    for(int i=1;i<=n;i++)
    {
        cin>>bus>>pri>>t;
        if(!bus)
        {
            //添加一张新票
            y++;
            tic[y].last=t+45;
            tic[y].price=pri;
            tic[y].used=false;
            sum+=pri;
        }
  //【4.公交的情况】
        else
        {
            bool can=false;//能否使用优惠票
            int newx=x;
            for(int j=x;j<=y;j++)
            {
                                //如果该票已过期就改编区间左端点的值
                if(tic[j].last<t)
                {
                    newx=j;
                    continue;
                }
  //如果能使用就立即退出循环并标记
                if((tic[j].price>=pri)&&(!tic[j].used))
                {
                    can=true;
                    tic[j].used=true;
                    break;  
                }
            }
  //刷新x的值
            x=newx;
  //刷新sum
  //如果can是true，sum就加0*pri
  //反之加1*pri
            sum+=(!can)*pri;
        }
    }
  //【5.输出及返回】
    cout<<sum<<endl;
    return 0;
}

总结

本题很适合作为PJ第二题，虽然算法简单但是考察耐心读题，**强烈建议大家先别急写代码，确认理解题意再写，能节省大量时间。**

温馨提示：“=zhu1YI1JIAN1cha6”

QaQ