oistr
2019-11-17 22:06:30
考都考了，那就发一篇吧
（我会把pj前三题的题解做个整合版发在lg博客里，敬请期待！）
这道题基本在意料之中，和龙虎斗类型相似的枚举模拟题，虽然算法简单但是小坑无数
看到这题第一反应是“这么简单的一题啊”
迅速开编。
直接模拟即可。开变量记录上一张票的截止时间，逢公交判断即可。
发现可以边读入边处理，节省空间
5min after...
诶肿么样例输错了？！[蒟蒻在线懵逼]
好再来康康...
诶！
由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票
woc...还有这个要求！
那好办，直接再开个变量记录上一次地铁票价，加一个判断就成。
3min后...
好，我们来看看第一个样例...啊！输对了！[蒟蒻的笑容]
然后突然扫到一句话：
如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。
woc!!还会有多张优惠票?!那...直接开一个变量记录的方法直接推翻。
[来自蒟蒻的尴尬而又不是礼貌的微笑]
于是决定开结构体数组存储票价信息。
然后又发现如果每次做公交时都从头遍历一遍所有票会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第二题，虽然算法简单但是考察耐心读题，强烈建议大家先别急写代码，确认理解题意再写，能节省大量时间。
QaQ