题意

$n$个人会在$t_i$时刻产生接水的想法，若$1 \dots i-1$没有人在排队，那么他会去排队；每个人接水的时间为$p$，求每个人接水完成的时间

数据范围：$1 \le n \le 100000,1 \le p \le 10^9,0 \le t_i \le 10^9$

题解

模拟题
用$3$个优先队列，分别储存

• 原序列
• 产生接水想法的人
• 正在排队的人

按题意模拟即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define int long long
const int N=100000+10;
int n,p;
int t[N];
int T;
int ans[N];
struct node{
    int ti,id;
    bool f;
    inline node(int ti=0,int id=0,bool f=0):ti(ti),id(id),f(f){}
    inline bool operator < (const node& x) const{
        return ti==x.ti?(f==x.f?id<x.id:f<x.f):ti<x.ti;
    }
};
set<node> a;
set<int> q,r;
signed main(){
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%lld",&t[i]);
        a.insert(node{t[i],i,0});
    }
    for(;!a.empty();){
        int ti=a.begin()->ti;
        int id=a.begin()->id;
        bool f=a.begin()->f;
        a.erase(a.begin());
        if(f==0){
            if(q.empty() || *q.begin()>id){
                q.insert(id);
                T=max(T,t[id])+p;
                a.insert(node{T,id,1});
            }
            else r.insert(id);
        }
        else{
            ans[id]=ti;
            q.erase(id);
            for(;!r.empty() && (q.empty() || *q.begin()>*r.begin());){
                int id=*r.begin();
                r.erase(r.begin());
                q.insert(id);
                T=max(T,t[id])+p;
                a.insert(node{T,id,1});
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    return 0;
}