题解：CF1239C Queue in the Train

· · 题解

前言

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

思路

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

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

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

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

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

以下设 now 表示当前的时间。

最开始把所有元素都加入到 noidea 中，然后开始迭代。

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

每一次更新：now \to now + p，并取出队列的队头元素，他的接水时间就是 now。

然后考虑 noidea中的元素，每一次找到堆顶，如果堆顶想加入的时间已经小于等于了 now ，他就应该离开 noidea。此时又分两种情况：

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

时间复杂度：O(n \log n)。

代码

#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]<<' ';//输出时间 
    }
}