Y • 2天前
using namespace std;
const int N = 1e5 + 10; // 最大操作数(根据题目约束调整,确保≥n) // 双数组模拟队列:存储优惠票的票价和生成时间(下标对应同一票) int price_q[N]; // 票价队列 int time_q[N]; // 生成时间队列 int hh = 0, tt = -1; // 队列指针:hh队头,tt队尾(初始为空)
int main() {
ios::sync_with_stdio(false); // 加速输入输出(处理大数据时避免超时)
cin.tie(nullptr);
int n;
cin >> n;
int total = 0; // 总花费
for (int i = 0; i < n; i++) {
int type, price, time;
cin >> type >> price >> time;
if (type == 0) { // 地铁:付费+生成优惠票(队尾插入)
total += price;
// 队列模板:向队尾插入元素(双数组同步插入)
price_q[++tt] = price;
time_q[tt] = time;
} else { // 公交车:尝试使用优惠票
// 第一步:清理队头所有过期的票(有效期>45分钟则弹出)
while (hh <= tt) { // 队列不为空(模板判空逻辑)
// 队列模板:取队头的值(不弹出)
int head_price = price_q[hh];
int head_time = time_q[hh];
if (time - head_time > 45) {
hh++; // 队列模板:从队头弹出(移动hh指针)
} else {
break; // 队头未过期,后续票更晚生成,无需继续检查
}
}
// 第二步:查找最早符合条件的票(从队头开始,FIFO优先级)
bool used = false;
// 遍历队列,找第一个票价≥公交车票价的票
for (int j = hh; j <= tt; j++) {
if (price_q[j] >= price) {
// 找到后,将该位置后续元素前移(覆盖当前元素,模拟删除)
for (int k = j; k < tt; k++) {
price_q[k] = price_q[k + 1];
time_q[k] = time_q[k + 1];
}
tt--; // 队尾指针左移,队列长度减1
used = true;
break; // 优先使用最早的票,立即退出
}
}
// 未使用优惠票,公交车需付费
if (!used) {
total += price;
}
}
}
cout << total << endl;
return 0;
}
评论:
请先登录,才能进行评论