题解：CF1239C Queue in the Train

前言

奇怪的 STL 应用题，但说实话比较考验思维。

思路

显然，对于每一个时刻，都有这三类人：

$noidea$ ：还没有进入等待队列的想法（就是没有到去接水的时间）。
$want$ ：想去接水但是不能到队列里面去。
$wait$ ：已经在等待的队列里面了。

对于第一个，我们用一个小根堆，来存他们想加入队列的时间，因为显然优先考虑想先去接水的人。同时要存储人的编号，因为你后面总会把这些人插到

want

或者

wait

里面去。如果想加入等待队列的时间一样，优先考虑编号小的。

对于第二个，同样用一个小根堆，这个是存编号。因为大家都想要去接水了，就要优先考虑编号小的。

对于第三个用一个普通队列即可。因为顺序已经定下来了，不可能去插队吧。而且题目中说了正在饮水机旁排队的所有人形成一个先进先出的队列。

这里就一个性质：等待队列里的数单调递减。
很简单，因为题目中说了只有比自己编号小的都没去自己才有资格去。
这个性质比较重要。

以下设

now

表示当前的时间。

最开始把所有元素都加入到

noidea

中，然后开始迭代。

考虑等待队列空了，有两种情况：

如果 $want$ 没空，让 $want$ 中编号最小的人插入到队列里面中。
$want$ 也空了，就从 $noidea$ 中取出堆顶元素，插入到队列中，并让 $now$ 等于堆顶元素想去接水的时间，因为中间肯定会出现空闲期，等空闲期结束了自然是这个人去接水。

每一次更新：

now \to now + p

，并取出队列的队头元素，他的接水时间就是

now

。

然后考虑

noidea

中的元素，每一次找到堆顶，如果堆顶想加入的时间已经小于等于了

now

，他就应该离开

noidea

。此时又分两种情况：

该元素编号大于了等待队列末尾元素。加入的话不满足上面说的性质，所以加到 $want$ 里面去。
否则就可以直接加到等待队列的末尾。

最后踢掉队头元素，因为他已经被考虑过了，所以对之后的过程就没有贡献了。

时间复杂度：

O(n \log n)

。

代码

CPP

#include<iostream>
#include<queue>
#define pii pair<long long,int>
int n;
const int N=3e5+10;
long long a[N],m;
using namespace std;
priority_queue<int,vector<int>,greater<int>> want;//想排队但是进不来 
priority_queue<pii,vector<pii>,greater<pii>> noidea;//根本就没想去排队 
queue<int> wait;//在队列中了 
long long now,ans[N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		noidea.push({a[i],i});
	}
	for(int i=1;i<=n;i++){
		if(wait.empty()){//如果队列已经空了 
			if(want.size()){//看看有没有想要进来的 
				wait.push(want.top());//加入编号最小的人 
				want.pop();//弹出 
			}else{//没有想要进来的人 
				wait.push(noidea.top().second);//硬拉一个不想来的人 
				now=noidea.top().first;
				noidea.pop();
			}
		}
		now+=m;
		ans[wait.front()]=now;//时间 
		while(noidea.size()&&now>=noidea.top().first){//是否到了排队的时候 
			if(wait.back()>noidea.top().second){//看看满不满足单调性 
				wait.push(noidea.top().second);
			}else{
				want.push(noidea.top().second);
			}
			noidea.pop();//考虑完了就删除。 
		}
		wait.pop();//踢掉 
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';//输出时间 
	}
}

题解：CF1239C Queue in the Train

文章操作

前言

思路

代码

相关推荐

评论

题解：CF1239C Queue in the Train