P5661 题解

ikunTLE · 2024-12-25 19:20:17 · 题解

题目传送门

思路

不难想到暴力思路：每次循环判断每一张优惠券是否在规定时间内。然而这样做的时间复杂度为 \mathcal{O}(n^2)，不可行。

考虑队列优化，每次判断时把前面已经超过 45 分钟的优惠券弹掉。这样做，时间复杂度降到了 \mathcal{O}(n)，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define front _front
#define back _back//防止重名
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
struct node{
    bool type;//类型
    int price,t;//命名如题意
}q[N];
int front,back=1;
int main(){
    int n=read(),ans=0;
    for(int i=1;i<=n;++i){
        node temp={(bool)read(),read(),read()};
        if(temp.type){//公交车
            bool flag=false;
            for(int j=back;j<=front;++j)
                if(temp.t-q[j].t<=45){//队列优化判断条件
                    if(temp.price<=q[j].price){
                        q[j].price=0;
                        flag=true;
                        break;
                    }
                }
                else back=j;//弹掉不符合条件的优惠券
            if(!flag)
                ans+=temp.price;
        }
        else{//地铁
            ans+=temp.price;
            q[++front]=temp;
        }
    }
    printf("%d\n",ans);
    return 0;
}