atcoder ABC 358-B题详解

atcoder ABC 358-B题详解

Problem Statement

At the entrance of AtCoder Land, there is a single ticket booth where visitors line up to purchase tickets one by one. The purchasing process takes A seconds per person. Once the person at the front of the line finishes purchasing their ticket, the next person (if any) immediately starts their purchasing process.

Currently, there is no one in line at the ticket booth, and N people will come to buy tickets one after another. Specifically, the i-th person will arrive at the ticket booth Ti​ seconds from now. If there is already a line, they will join the end of it; if not, they will start the purchasing process immediately. Here, T1​<T2​<⋯<TN​.

For each i (1≤i≤N), determine how many seconds from now the i-th person will finish purchasing their ticket.

Constraints

1≤N≤100
0≤T1​<T2​<⋯<TN​≤106
1≤A≤106
All input values are integers.

Input

The input is given from Standard Input in the following format:

N A
T1​ T2​ … TN​

Output

Print N lines. The i-th line should contain the number of seconds from now that the i-th person will finish purchasing their ticket.

Sample Input 1

3 4
0 2 10

Sample Output 1

4
8
14
The events proceed in the following order:

At 0 seconds: The 1st person arrives at the ticket booth and starts the purchasing process.
At 2 seconds: The 2nd person arrives at the ticket booth and joins the line behind the 1st person.
At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person starts the purchasing process.
At 8 seconds: The 2nd person finishes purchasing their ticket.
At 10 seconds: The 3rd person arrives at the ticket booth and starts the purchasing process.
At 14 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 2

3 3
1 4 7

Sample Output 2

4
7
10
The events proceed in the following order:

At 1 second: The 1st person arrives at the ticket booth and starts the purchasing process.
At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person arrives at the ticket booth and starts the purchasing process.
At 7 seconds: The 2nd person finishes purchasing their ticket, and the 3rd person arrives at the ticket booth and starts the purchasing process.
At 10 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 3

10 50000
120190 165111 196897 456895 540000 552614 561627 743796 757613 991216

Sample Output 3

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216

思路分析：

本题需要求解每一个人需要的时间，a是解答问题的时间，需要求上一个人的时间加a和当前值加a取最大值，即可以求得每一个人的时间。

code：

#include <iostream>
#include <cmath>
using namespace std;
int n,a;
const int N=110;
int t[N];
int t1[N];//存答案
int main(){
    cin>>n>>a;
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    t[0]=0;
    t[n+1]=0;//处理边界
    for(int i=1;i<=n;i++){
        t1[i]=max((t1[i-1]+a),(t[i]+a));
    }
    for(int i=1;i<=n;i++){
        cout<<t1[i]<<endl;
    }
}