题解 P5661 【公交换乘【民间数据】】

· · 题解

作为一个这道题只得了20分的选手，回家后便做了10分钟，净做出来了！O2优化的功能的确很强呀！

考场上写了一个队列，样例过了，但其实有一个bug：

假设有很多的优惠券的话，每用一个，这个队列只有队首元素回pop 真正没有用的还在保留着......

于是，回到了家中，变对这道题进行了改进：

这个队列只能进，用vis[ ]打标记

看看这个优惠券有没有用过

于是，每一次要选优惠券的时候，便把队列从头到尾遍历

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int n,head=1,tail,price[100010],t[100010],car[100010],quan,ans,vis[100010];
struct node
{
    int time_,have;
}q[100010];
int finding(int tt,int mm)
{
    for(int i=head;i<=tail;i++) if(tt-q[i].time_<=45&&quan>=1&&mm<=q[i].have&&vis[i]==0) return i;
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>car[i]>>price[i]>>t[i];
    for(int i=1;i<=n;i++)
    {
        if(car[i]==0)
        {
            quan++;
            ans+=price[i];
            tail++;
            q[tail].have=price[i];
            q[tail].time_=t[i];
        }
        else
        {
            int flag=finding(t[i],price[i]);
            if(flag!=0) 
            {
                quan--;
                vis[flag]=1;
            }
            else ans+=price[i];
        }
    }
    cout<<ans<<endl;
}