算法
(滑动窗口,队列) $O(45n)$
这道题目有个限制很重要:
不会有两次乘车记录出现在同一分钟
这就说明对于每个公交车来说,所能使用的优惠券不会超过45张。即我们可以完美避开各种复杂的数据结构优化了。
因此我们可以从前往后扫描每条记录,同时用一个队列维护当前车次可以使用的优惠券区间:
- 如果当前记录是火车,则加入维护的优惠券区间;
- 如果当前记录是公交车,则线性扫描一遍队列中所有优惠券,找到第一个未被使用过的且大于等于当前价格的优惠券即可;
- 可以用一个
bool
数组对优惠券判重,以保证每张优惠券最多只被用一次。
时间复杂度
最坏情况下,对于每条公交车记录都需要遍历45张优惠券,因此时间复杂度是 $O(45n)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Ticket
{
int time, price;
}q[N];
bool st[N];
int main()
{
scanf("%d", &n);
int res = 0;
for (int i = 0, l = 0, r = 0; i < n; i ++ )
{
int type, price, time;
scanf("%d%d%d", &type, &price, &time);
if (type == 0)
{
q[r ++ ] = {time, price};
res += price;
}
else
{
while (l < r && time - q[l].time > 45) l ++ ;
bool success = false;
for (int j = l; j < r; j ++ )
if (!st[j] && q[j].price >= price)
{
st[j] = true;
success = true;
break;
}
if (!success) res += price;
}
}
printf("%d\n", res);
return 0;
}
苗啊
y总本人!!!
tql
666
妙啊