题目描述
见原题链接
算法1
(模拟、队列) $O(45N)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct Ticket //建一个结构体手动维护队列
{
int time,price; //乘车时间、价格
bool used; //是否已经使用过优惠券
} t[N];
int res;
int main()
{
scanf("%d",&n);
for(int i=0,l=0,r=0; i<n; i++)
{
int type,pri,tt;
scanf("%d%d%d",&type,&pri,&tt);
if(type==0)
{
res=res+pri; //地铁不能免票
t[r++]= {tt,pri}; //地铁的优惠券存入队列
}
else
{
while(l<r&&tt-t[l].time>45)l++; //维护滑动窗口,即保持区间在45分钟内
bool suc=false; //是否成功找到优惠券
for(int j=l; j<r; j++) //遍历队列
{
if(!t[j].used&&t[j].price>=pri)
{
t[j].used=true;
suc=true;
break;
}
}
if(!suc) res=res+pri; //如果没有找到,就需要购买车票
}
}
cout<<res<<endl;
return 0;
}