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

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

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

Why?

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

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