题解：P5661 [CSP-J2019] 公交换乘

思路

按题意模拟。
用一个双端队列来存优惠票价和获得时间。
如果坐地铁，花费相应的钱数并且往双端队列里面塞一个优惠票。因为输入数据的时间递增，所以双端队列里优惠票的获得时间也是递增。
如果坐公交，先把过期的优惠票从双端队列里面删除，然后判断队首的票价是否能够使用。如果不能够，就把这张票塞到另外一个栈里面存着，并把这张票从双端队列中删除，重复这个过程。如果双端队列空了还没有能用的票，就得原价坐公交车，否则删除能用的票，免费坐公交车。最终还要把存在栈里面的票从队首塞回双端队列里。
因为票的有效期只有

45

分钟，所以双端队列里面最多只有

45

张票，时间复杂度为

O(45n)

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
struct node{
	int t,val;
};
deque<node>q;
stack<node>s;
int n;
int opt,val,t;
int sum;

int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d%d%d",&opt,&val,&t);
		while(!q.empty()&&t-q.front().t>45)q.pop_front();
		if(opt){
			bool f=0;
			while(!q.empty()){
				if(q.front().val>=val){
					f=1;
					q.pop_front();
					break;
				}
				s.push(q.front());
				q.pop_front();
			}
			while(!s.empty()){
				q.push_front(s.top());
				s.pop();
			}
			if(!f)sum+=val;
		}
		else{
			sum+=val;
			q.push_back({t,val});
		}
	}
	printf("%d",sum);
	return 0;
}

题解：P5661 [CSP-J2019] 公交换乘

文章操作

思路

代码

相关推荐

评论

题解：P5661 [CSP-J2019] 公交换乘