我不会算这玩意的时间复杂度(虽然是AC代码)
查看原帖
我不会算这玩意的时间复杂度(虽然是AC代码)
520544
Phrvth楼主2022/8/12 21:30
#include<bits/stdc++.h>

using namespace std;
struct node{int v,t;};
int n,ans,price,ti,flag;
deque<node> q;
void add(int v,int t){q.push_back(node{v,t});}
void back(stack<node> s){while(!s.empty()) q.push_front(s.top()),s.pop();}
int solve(int v,int t){
	int sum=0;
	stack<node> s;
	while(!q.empty()&&t-q.front().t>45) q.pop_front();
	while(!q.empty()&&v>q.front().v) s.push(q.front()),q.pop_front();
	if(q.empty()) back(s),sum=v;
	else q.pop_front(),back(s);
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>flag>>price>>ti;
		if(flag==0) ans+=price,add(price,ti);
		else ans+=solve(price,ti);
	}
	cout<<ans<<endl;
	return 0;
}
2022/8/12 21:30
加载中...