公交换乘(transfer)题解

Peanut_Tang · 2019-11-24 14:19:07 · 题解

T2 公交换乘(transfer)

30pt

对于每个地铁，暴力把前面的公交都搜一遍，找到一个最早满足的即可。

复杂度是 O(n^2) 的。

60pt

考虑 price_i 都相同的部分分。

发现 t_i 两两不相同，又有 t_{bus}-t_{subway}≤45 ,所以对于每个地铁，最多只有 45 个公交满足，那么我们开一个队列，时间之差超过 45 的 pop 掉，对于每个地铁选 front 即可。

复杂度是 O(Cn) 的，其中 C=45 。

100pt

还是这个关键条件：对于每个地铁，最多只有 45 个公交满足。

法一：

那么我们可以开一个队列维护，和 60 的做法一样，时间之差超过 45 的 pop 掉，用掉的优惠券打个标记就好了。

复杂度是 O(Cn) 的，其中 C=45 。

法二：

发现优惠券要支持中间删除。

那么我们可以用链表维护优惠券，时间之差超过 45 的删掉，用掉的优惠券也删掉就好了。

链表删除的是 O(1) 的，查询是 O(C) 的。

复杂度是 O(Cn) 的，其中 C=45 。

法三：

不要那么多技巧，直接数组暴力维护，删除一个元素以后直接暴力把后面的都往前移，最多只会进行 4 次暴力移的操作。

所以复杂度是 O(Cn) 的，其中 C=180 。

Code:

#include <cstdio>
#define il inline
using namespace std;

int n,ans;
struct quan
{
    int t,p;
}q[100001];
int sze;

il int read()
{
    int res=0,sign=1;
    char c;

    while ((c=getchar())<'0'||c>'9') if (c=='-') sign=-1;

    res=c-'0';
    while ((c=getchar())>='0'&&c<='9') res=res*10+c-'0';

    return res*sign;
}

int main()
{
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);

    n=read();
    int i,j,g,opt,p,t;
    for (i=1; i<=n; i++)
    {
        opt=read(),p=read(),t=read();
        if (opt==0)
            ans+=p,q[++sze]=(quan){t,p};
        else
        {
            g=0;
            for (j=1; j<=sze; j++)
            {
                if (t-q[j].t<=45&&q[j].p>=p)
                {
                    g=j;
                    break;
                }
            }

            if (g==0) ans+=p;
            else
            {
                for (j=g+1; j<=sze; j++)
                {
                    q[j-1]=q[j];
                }
                sze--;
            }
        }

        g=0;
        for (j=1; j<=sze; j++)
        {
            if (t-q[j].t>45) g++;
        }
        for (j=g+1; j<=sze; j++)
        {
            q[j-g]=q[j];
        }
        sze-=g;
    }

    printf("%d",ans);

    return 0;
}