社区讨论
大佬们!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 条回复,欢迎继续交流。
正在加载回复...