已ac

Y  •  2天前


include

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;

}


评论:

请先登录,才能进行评论