社区讨论

大佬们!45分,剩下TLE,求调,AC必关!

P5661[CSP-J 2019] 公交换乘参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m20dipp5
此快照首次捕获于
2024/10/08 19:44
去年
此快照最后确认于
2025/11/04 17:38
4 个月前
查看原帖
45分,剩下TLE,求调,时间复杂度n^2
CPP
#include<iostream>
using namespace std;
struct type{
	int first;
	int second;
};
type q[100010];//手写队列
int beginn=0;
int endd=0;
void push(type x){
	q[endd++]=x;
}
type front(){
	return q[beginn];
}
void pop(){
	beginn++;
}
bool empty(){
	return beginn==endd;
}
int main(){
	int n;
	cin>>n;
	
	
	long long ans=0;
	for(int i=1;i<=n;i++){
		int opt,p,t;
		cin>>opt>>p>>t;
		if(opt==0){//地铁就加进队列里
			ans+=p;
			push({p,t});
		}else{     //公交就找有没有能用的优惠卷
			bool flag=1;
			for(int i=beginn;i<=endd;i++){//遍历一遍队列
				if(q[i].first==0x7ffffff&&q[i].second==0x7ffffff) continue;
				type k=q[i];
				int p1=k.first;
				int t1=k.second;
				if(t-t1<=45&&p1>=p){flag=0; q[i]={0x7ffffff,0x7ffffff}; break;}  //这里是为了让时间复杂度不变成n^3才这样做的,懒得写链表了
			}
			if(flag==1){//没有优惠卷可以用,要用钱
				ans+=p;
			}
		}
	}
	cout<<ans;
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...