codeforces 1239 C

一开始没有get到题目要点，然后一个set贪心wa了
然后发现了一个很恐怖的东西，比方说3在打水，这个时候2想喝水然后1想喝水，然后2就会排在1前面。。。
这就需要我们另外维护一个东西，排队的序列，
发现我们在把人丢进set时，要检测一下他是不是想喝水的里面下标最小的，是的话直接丢进队列里，不然话丢进set里
稍加思考我们发现 对于排队的队列，一定是一个递减的序列， 容易证明：
如果后面的id比前面的人大，那他看到自己前面有人去打水，他就根本不会去排队了，
所以我们直接维护一个队列就行了，比较的时候就比较队列的最后一个数和当前这个数哪个小来决定这个人是去排队，还是丢进想喝水的set里

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
struct Node{
    ll id,time;
}node[N];
ll n,p,ans[N],q[N],t[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>node[i].time;
        node[i].id=i;
        t[i]=node[i].time;
    }
    sort(node+1,node+1+n,[](Node a,Node b){return a.time<b.time||a.time==b.time&&a.id<b.id;});
    set<int>st;//want
    int j=1,l=0,r=0;
    ll now = 0;
    while (j<=n || !st.empty() || l != r){
        if(l == r && !st.empty()){
            q[++r]=*st.begin();
            st.erase(st.begin());
        }
        if(l == r){
            q[++r]=node[j++].id;
        }
        now = max(now,t[q[++l]]) + p;
        ans[q[l]]=now;
        while (node[j].time<=now&&j<=n){
            if(node[j].id<q[r]){//排队去了
                q[++r]=node[j++].id;
            }else{
                st.insert(node[j++].id);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
}