我太逊

蒙自二中 卢建铮(听风凭引)  •  1年前


include

using namespace std; const int MAXN = 100005; struct Ticket {

//赠票的价格,最晚使用时间和是否需用过
int price, time, used;

} q[MAXN];//赠票盒子 int head, tail, n, cost;

int main() {

cin >> n;
for (int i = 0; i < n; ++i) {
    int op, price, time;
    //输入每次坐车的种类,价格和发车时间
    cin >> op >> price >> time;
    if (op == 0) {
        //如果是坐地铁,直接把价格加到cost里面
        cost += price;
        //新一张赠票插入数组末尾,这张票的最晚使用时间是当前时间+45
        q[tail].time = time + 45;
        //赠票面额就是地铁票价
        q[tail++].price = price;
    } else {
        //先用一个循环把过期票扔掉
        while (head < tail && q[head].time < time) {
            head++;
        }
        bool found = false;//表示是否有合适的赠票,先假设没有
        for (int j = head; j < tail; ++j) {
            //循环所有剩余的票,这些一定都没过期,因为题目中时间是按顺序给我们的
            if (q[j].price >= price && q[j].used == 0) {
                //如果价格合适,并且没用过,标记找到了,这张票标记用过
                found = true;
                q[j].used = 1;
                break;
            }
        }
        //如果没找到合适的赠票,老老实实花钱买吧
        if (!found) cost += price;
    }
}
cout << cost << endl;
return 0;

}


评论:

请先登录,才能进行评论