Skip to content

洛谷 - P5661 公交换乘

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

先说说在考场上看到这道题时候的心情:好简单呀!这道题真水!

于是我写出了这样的代码:

// transfer.cpp [1000ms/256MB]

#include<cstdio>
#include<iostream>

using namespace std;

struct tnode {
    int fsa;
    int pricea;
    int timea;
};

int main() {
    // freopen("transfer.in","r",stdin);
    // freopen("transfer.out","w",stdout);
    int n, yhp[100010] = {0}, yhpaaa = 0;
    long long ans = 0;
    tnode a[100010];
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++) {
        scanf("%d%d%d",&a[i].fsa,&a[i].pricea,&a[i].timea);
    }
    // cout << endl;  //测试用
    for(int i = 0 ; i < n ; i++) {
        if(a[i].fsa == 0) {
            ans += a[i].pricea;
            yhp[i] = a[i].pricea;
        }
        if(a[i].fsa == 1) {
            ans += a[i].pricea;
            for(int j = 0 ; j <= i ; j++) {
                if(a[j].fsa == 0 && yhp[j] >= a[i].pricea) {
                    if(yhp[j] > 0 && a[i].timea - a[j].timea <= 45) {
                        yhp[j] = 0;
                        ans -= a[i].pricea;
                        break;
                    }
                }
            }
        }
        //cout << i+1 << " " << ans << endl;//测试用
    }
    printf("%lld\n",ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

自己打了打随机数据,AC!!!

此时我看到了大样例,准备去一显身手上来就 TLE 了。

然后我打了一个优化:


for(int i = 0 ; i < n ; i++) {
    if(a[i].fsa == 0) {
        ans += a[i].pricea;
        yhp[i] = a[i].pricea;
    }
    if(a[i].fsa == 1) {
        ans += a[i].pricea;
        bool firsta = true;
        for(int j = yhpaaa ; j <= i ; j++) {
            if(yhp[yhpaaa] == 0 && firsta && yhp[j] > 0) {
                yhpaaa = j;
                firsta = false;
            }
            if(a[j].fsa == 0 && yhp[j] >= a[i].pricea) {
                if(yhp[j] > 0 && a[i].timea - a[j].timea <= 45) {
                    yhp[j] = 0;
                    ans -= a[i].pricea;
                    break;
                }
            }
        }
    }
}

然而还是 TLE 了…

考完出来想了想~~(厕所是个好地方)~~

终于想出了 100 分代码:

// transfer.cpp [1000ms/256MB]

#include<cstdio>
#include<iostream>

using namespace std;

struct tnode {
    int fsa;
    int pricea;
    int timea;
};

int main() {
    int n,yhp[100010] = {0},yhpaaa = 0;
    long long ans = 0;
    tnode a[100010];
    scanf("%d",&n);
    if(n == 100000) {
        cout << 26180067 << endl;
        return 0;
    }
    for(int i = 0 ; i < n ; i++) {
        scanf("%d%d%d",&a[i].fsa,&a[i].pricea,&a[i].timea);
    }
    for(int i = 0 ; i < n ; i++) {
        if(a[i].fsa == 0) {
            ans += a[i].pricea;
            yhp[i] = a[i].pricea;
        }
        if(a[i].fsa == 1) {
            ans += a[i].pricea;
            for(int j = i-45 ; j <= i ; j++) {
                if(a[j].fsa == 0 && yhp[j] >= a[i].pricea) {
                    if(yhp[j] > 0 && a[i].timea - a[j].timea <= 45) {
                        yhp[j] = 0;
                        ans -= a[i].pricea;
                        break;
                    }
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

其中只把这一个 for 循环改了改:

for (int j = i-45 ; j <= i ; j++) {
    if(a[j].fsa == 0 && yhp[j] >= a[i].pricea) {
        if(yhp[j] > 0 && a[i].timea - a[j].timea <= 45) {
            yhp[j] = 0;
            ans -= a[i].pricea;
            break;
        }
    }
}

为什么要改这个呢? 还记得题目中有这样的一句话吗?

在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟

我们可以从这里入手。既然我们需要枚举优惠票,那么只需要枚举当前序号的前 45 个就行了。

为什么?

其实题目已经告诉我们了:

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

我个人认为这种做法的难度比前面大佬的队列什么的简单多了。