yz总题解; https://www.acwing.com/solution/content/6405/
算法1:队列维护(模拟) $O(45*n)$
//用队列记录所有的优惠卷,每次查询优惠卷时,先出队过期的,然后再查找
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
PII yhj[N];
int n, hh = 1, tt = 0, res; //队列从1开始使用,也可从0开始使用,注意好边界就可以
int main() {
scanf("%d", &n);
int t, x, op;
while (n--) {
scanf("%d%d%d", &op, &x, &t);
if (op == 0) yhj[++tt] = {t, x}; //记录优惠卷
else {
while (hh <= tt && t - yhj[hh].first > 45) hh++; //过滤掉过期的
for (int i = hh; i <= tt; ++ i) //在没有过期的里面找最靠前的可用优惠卷
if (yhj[i].second >= x) {
x = 0;
yhj[i].second = 0;
break;
}
}
res += x;
}
printf("%d", res);
return 0;
}