1 条题解

  • 1
    @ 2025-2-9 11:00:18
    #include <bits/stdc++.h>
    using namespace std;
    
    /*
    有多张优惠票满足条件,
    则优先消耗获得最早的优惠票
    
    1.坐地铁
    买票
    获得等额的优惠券:金额、获得时间、是否使用过
    
    2.坐公交
    在有效期内的优惠券中,查找第1张金额>=公交票价的优惠券
    找到:使用该优惠券
    找不到:买票
    
    使用队列,维护优惠券的信息
    */
    const int N = 1e5 + 10;
    struct node{
        int price,time;
        bool used;
    }q[N];//优惠券的队列
    int h = 1,t = 0;
    int n,ans = 0;
    
    int main(){
        scanf("%d",&n);
        int type,money,start;
        for(int i = 1;i <= n;i++){
            scanf("%d%d%d",&type,&money,&start);
            //如果是地铁
            if(type == 0){
                //买票,获得优惠券
                ans += money;
                t++;
                q[t].price = money;
                q[t].time = start;
                q[t].used = false;//默认没有使用
            }else{
                //公交
                //丢弃过期的优惠期
                while(h<=t&&start-q[h].time>45) h++;
    
                bool f = false;//假设没找到
                //在有效期内的优惠券,找第一张>=公交票价的 且 没有用过的优惠券
                for(int j = h;j <= t;j++){
                    if(q[j].price >= money && q[j].used == false){
                        q[j].used = true;
                        f = true;
                        break;
                    }
                }
    
                //如果没有找到能用的优惠券,买票
                if(f == false) ans += money;
            }
        }
    
        printf("%d",ans);
    	return 0;
    }
    • 1

    信息

    ID
    291
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    149
    已通过
    56
    上传者