[CSP-J2019] 公交换乘 原题

鉴于本人实力过低，代码只在O2优化下AC QAQ
此系列并非题解或讲解（你愿意看我也不制止，就是不一定能看懂），只是自己留着看

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, price, time_go, cost_all, trans_choose, ticket_num;
struct ticket {
    int end_time;
    bool ticket_used = true; //没有票或用过的票都为true 
    int ticket_worth;
};
ticket have_ticket[N];

void test() {
    cout << endl;
    for (int i = 0; i < ticket_num; i++) {
        cout << have_ticket[i].ticket_used << " " << have_ticket[i].end_time << endl;
    }
    cout << cost_all << endl << endl;
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> trans_choose >> price >> time_go;
        if (trans_choose == 0) { //乘地铁 
            have_ticket[ticket_num].ticket_used = false; //获得一张票 
            have_ticket[ticket_num].end_time = time_go + 45; //计算过期时间 
            have_ticket[ticket_num].ticket_worth = price;
            ticket_num++;
            cost_all += price;
        } else { //乘公交 
            bool use_ticket = false;
            if (i == 0) { //特判 
                cost_all += price;
            } else {
                for (int j = 0; j < ticket_num; j++) {
                    if (!have_ticket[j].ticket_used) { //找到最早的没用过且没过期的票 
                        if (have_ticket[j].end_time < time_go) { //如果过期了标记为true 
                            have_ticket[j].ticket_used = true;
                        } else { //票还能用 
                            if (have_ticket[j].ticket_worth >= price) {
                                have_ticket[j].ticket_used = true; //使用这张票 
                                use_ticket = true;
                                break;
                            }
                        }
                    }
                }
                if (!use_ticket) {
                    cost_all += price;
                }
            }
        }
        //test();
    }
    cout << cost_all << endl;
    return 0;
}