C++14(g++5.4) 解法, 执行用时: 88ms, 内存消耗: 6836K, 提交时间: 2019-12-10 14:50:33

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
#define ll long long
struct node
{
    int id;
    ll p;
}a[maxn];
 
bool cmp(const node &A,const node &B)
{
    if(A.p==B.p) return A.id<B.id;
    return A.p<B.p;
}
 
bool operator<(const node &A,const node &B)
{
    return A.id>B.id;
}
priority_queue <node> q;
 
ll ans[maxn];
 
 
int main()
{
    int n;
    ll k,y;
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&y);
        a[i]=(node){i,y};
    }
    sort(a+1,a+n+1,cmp);
    int l=0;
    ll tmp=0;
    for(int i=1;i<=n;i++)
    {
        if(q.empty())
        {
            q.push(a[++l]);
        }
        node u=q.top();
        q.pop();
        ans[u.id]=max(tmp+k,u.p+k);
        tmp=ans[u.id];
 
        while(a[l+1].p<=tmp&&l<n)
        {
            q.push(a[++l]);
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",ans[i]);
    }
 
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 119ms, 内存消耗: 4752K, 提交时间: 2019-12-17 19:50:37

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std; 
typedef long long ll;
pair<int,int>t[100005];
ll ans[100005];
int main()
{
	ll n,p;
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>t[i].first,t[i].second=i;
	sort(t+1,t+1+n);
	priority_queue< int , vector<int> , greater<int> >q;
	ll now=0;
	for(int i=1;i<=n;i++)
	{
		if(t[i].first<=now){
			q.push(t[i].second);
			continue;
		}
		if(q.empty())
		{
			now=t[i].first+p;
			ans[t[i].second]=now;
		}
		else
		{
			int x=q.top();q.pop();
			ans[x]=now+p;
			now+=p;
			i--;
		}
	}
	while(!q.empty())
	{
		int x=q.top();q.pop();
		ans[x]=now+p;
		now+=p;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}