1 条题解

  • 0
    @ 2025-10-10 19:32:48

    C++ :

    #include<bits/stdc++.h>
    using namespace std; 
    /*
    维护45分钟的滑动窗口(队列实现),来存储当前可用的优惠券: 
    1、如果是当前是地铁票,先买票,然后将优惠券存入滑动窗口;
    2、如果当前是公交车:
    	从滑动窗口中,找出第1个没有被用过的,且金额>=当前票价的优惠券;
    	找到:标记该优惠券使用;
    	没找到:只能买票!
    */
    
    const int N = 100010;
    int n;
    struct ticket{
    	int time,price;//时间,价格
    	bool used;//该票是否使用 
    }tk[N];
    
    int main() {
    	scanf("%d",&n);
    	int l = 0,r = 0;//头尾指针 
    	int res = 0;
    	int type,price,time;
    	for(int i = 0;i < n;i++){
    		scanf("%d%d%d",&type,&price,&time);
    		//如果是乘坐地铁
    		if(type == 0){
    			res = res + price;
    			//存储优惠券 
    			tk[r].time = time;
    			tk[r].price = price; 
    			r++;
    		} else{
    			//弹出所有不在区间内的票
    			while(l < r && time - tk[l].time > 45) l++; 
    			
    			bool f = false;//假设没找到可用的优惠券
    			for(int i = l;i < r;i++){
    				//如果有优惠券没有用过,且价格超过当前的票价
    				if(tk[i].used==false && tk[i].price >= price){
    					tk[i].used = true;
    					f = true;
    					break;
    				}
    			}
    			
    			//如果没有优惠券,买票 
    			if(!f) res += price; 
    		} 
    	}
    	
    	//输出票价 
    	printf("%d\n",res);
    	return 0;
    }
    
    • 1

    信息

    ID
    853
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者