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

_LHF_ · 2019-11-18 12:29:14 · 题解

2019CSP-J第二题，大概是考场上遇到突发性脑残，相处了一种丧心病狂做法（官方数据只能拿80分）：

我在CSP复赛的时候，做这一题没想太多，竟然不知道就是一道队列的题目。但是，我使用了一种丧心病狂的做法。

首先，借助C++ STL的优势，我开了1000个小根堆（其实每一个小根堆就是一个价格的桶），然后每一次看价格比公交车大的桶，最后选出时间最小有符合题意的一个，时间复杂度上限大约是是O(n log(n/price)*price)。

行吧，别的话不多说，上代码：

#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q[1010];
int T,t,a,b,w,ans,mx;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&w,&a,&b);
        if(a>mx) mx=a;
        if(w)
        {
            w=0;
            t=0x7fffffff;
            for(int i=a;i<=mx;i++)
            {
                while(!q[i].empty())
                {
                    if(b-q[i].top()<=45)
                    {
                        if(q[i].top()<t)
                        {
                            t=q[i].top();
                            w=i;
                        }
                        break;
                    }
                    else q[i].pop();
                }
            }
            if(w) q[w].pop();
            else ans+=a;
        }
        else
        {
            q[a].push(b);
            ans+=a;
        }
    }
    printf("%d",ans);
    return 0;
}

更新：2019.12.8

但是这种做法只能拿80分！

其实，我们不需要使用小根堆，因为题目中有说到这么一句话:

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

根据上面的代码的思路，我们是先找时间最少的那一个，然后看行不行，在继续往后看。如果利用了这一点，我们可以把小根堆换成普通队列，因为队首的那一个元素肯定是那种价格中时间最小的。

所以，这样子的时间复杂度上线就是O(n*price)，正常都可以AC这一道题目。

好了，上代码：

#include<queue>
#include<cstdio>
using namespace std;
queue<int> q[1010];
int T,t,a,b,w,ans,mx;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&w,&a,&b);
        if(a>mx) mx=a;
        if(w)
        {
            w=0;
            t=0x7fffffff;
            for(int i=a;i<=mx;i++)
            {
                while(!q[i].empty())
                {
                    if(b-q[i].front()<=45)
                    {
                        if(q[i].front()<t)
                        {
                            t=q[i].front();
                            w=i;
                        }
                        break;
                    }
                    else q[i].pop();
                }
            }
            if(w) q[w].pop();
            else ans+=a;
        }
        else
        {
            q[a].push(b);
            ans+=a;
        }
    }
    printf("%d",ans);
    return 0;
}

最后插入一则广告：本蒟蒻2019CSP-J只考了380分，因为第二题只拿了80分（v_v），希望大家吸取我的教训，争取AK明年的CSP！