Skip to content

洛谷 - P5661 公交换乘

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

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

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

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 了。

然后我打了一个优化:

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

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 循环改了改:

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 个就行了。

为什么?

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

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

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