题解：P10711 [NOISG 2024 Prelim] Amusement Park

两种团队的上车方式不同，所以分开处理。

又因为每个团队只会上车一次，所以我们可以暴力地修改每个团队的上车情况，并每次从当前编号最小的团队开始上车。

设置当前车剩下的名额为

b

，对于下一个团队，如果能拆开，则直接让其上车，需要维护这类团队的编号的最小值，可以使用对顶堆维护。如果不能拆开，则要找到下一个能上车的团队，需要找到这类团队的下一个编号最小的价值小于等于

b

的位置，这个可以用线段树二分，或者平衡树维护。

复杂度

O(q \log q)

CPP

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
const int INF=1e18;
struct node{
	int l,r,mn;
};
node tr[N*4];
#define ls u<<1
#define rs u<<1|1
inline void up(int u){
	tr[u].mn=min(tr[ls].mn,tr[rs].mn);
}
inline void build(int u,int l,int r){
	tr[u].l=l;tr[u].r=r;
	if(l==r){
		tr[u].mn=INF;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	up(u);
}
inline void cg(int u,int x,int k){
	if(tr[u].l==x&&tr[u].r==x){
		tr[u].mn=k;
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid){
		cg(ls,x,k);
	}
	else{
		cg(rs,x,k);
	}
	up(u);
}
inline int find(int u,int x){
	if(tr[u].l==tr[u].r){
		return tr[u].mn<=x?tr[u].l:-1;
	}
	int ans=-1;
	if(tr[ls].mn<=x){
		ans=find(ls,x);
	}
	else if(tr[rs].mn<=x){
		ans=find(rs,x);
	}
	return ans;
}
struct Node{
	int id;
	bool operator<(const Node &x) const{
		return x.id<id;
	}
};
int ww[N];
priority_queue<Node> q,fq;
inline void qcl(){
	while(q.size()&&fq.size()&&q.top().id==fq.top().id){
		q.pop();fq.pop();
	}
}
int lx[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int qq;
	cin>>qq;
	int cnt=0;
	build(1,1,200000);
	for(int i=1;i<=qq;i++){
		int op;cin>>op;
		if(op==1){
			++cnt;
			cin>>ww[cnt]>>lx[cnt];
			if(lx[cnt]==0){
				cg(1,cnt,ww[cnt]);
			}
			else{
				q.push({cnt});
			}
		}
		if(op==2){
			int x;cin>>x;
			if(lx[x]==0){
				cg(1,x,INF);
			}
			else{
				ww[x]=0;
				fq.push({x});
				qcl();
			}
		}
		if(op==3){
			int b;cin>>b;
			vector<int> ansid,ansvl;
			while(b){
				qcl();
				int fdw=find(1,b);
				if(!q.size()&&fdw==-1){
					break;
				}
				else if(!q.size()&&fdw!=-1){
					int id=fdw;
					ansid.push_back(id);
					ansvl.push_back(ww[id]);
					cg(1,id,INF);b-=ww[id];
				}
				else if(q.size()&&fdw==-1){
					int id=q.top().id;
					if(ww[id]<=b){
						ansid.push_back(id);
						ansvl.push_back(ww[id]);
						q.pop();b-=ww[id];
					}
					else{
						ansid.push_back(id);
						ansvl.push_back(b);
						ww[id]-=b;b=0;
					}
				}
				else{
					if(q.top().id>fdw){
						int id=fdw;
						ansid.push_back(id);
						ansvl.push_back(ww[id]);
						cg(1,id,INF);b-=ww[id];	
					}
					else{
						int id=q.top().id;
						if(ww[id]<=b){
							ansid.push_back(id);
							ansvl.push_back(ww[id]);
							q.pop();b-=ww[id];
						}
						else{
							ansid.push_back(id);
							ansvl.push_back(b);
							ww[id]-=b;b=0;
						}
					}
				}
			}
			cout<<ansid.size()<<endl;
			for(int j=0;j<ansid.size();j++){
				cout<<ansid[j]<<" "<<ansvl[j]<<endl;
			}
		}
	}
	
	return 0;
}

题解：P10711 [NOISG 2024 Prelim] Amusement Park

文章操作

相关推荐

评论

题解：P10711 [NOISG 2024 Prelim] Amusement Park