Skip to content

洛谷 - P5661 公交换乘

题解860 字
# 洛谷 # 模拟 # CSP-J # NOIP # 2019
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 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 了。

然后我打了一个优化：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 分代码：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 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 循环改了改：

C++
1
2
3
4
5
6
7
8
9
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 个就行了。

为什么？

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

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

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