AcWing 5060:排队打饭 ← 复旦大学考研机试题

【题目来源】
https://www.acwing.com/problem/content/description/5063/

【题目描述】
有 n 个同学在同一个食堂窗口排队打饭,按照到达队伍的时间顺序,从先到后依次编号为 1∼n。
其中,第 i 个同学的到达队伍时刻为
ai,打饭耗时为 ti
每个同学的耐心都是有限的,第 i 个同学的最大等待时间为
bi,即如果其在第 ai+bi 时刻还没有开始打饭,他就会离开队伍,放弃打饭。
在一个同学打完饭后,下一个同学会立即开始打饭,中间的时间损耗忽略不计。
例如,如果一个同学在时刻 1 开始打饭,打饭耗时为 3,那么他会在时刻 4 打完饭,而下一个同学也会在时刻 4 开始打饭。
请你计算,每个同学的开始打饭时刻。

【输入格式】
第一行包含整数 n。
接下来 n 行,其中第 i 行包含三个整数 ai,ti,bi。

【输出格式】
共一行,输出 n 个整数,其中第 i 个整数表示第 i 个同学的开始打饭时刻,如果该同学放弃打饭,则输出 -1。

【数据范围】
1≤n≤10^5 ,
1≤ai,ti,bi≤
10^9
数据保证 a1<a2<…<an。

【输入样例】
4
1 3 3
2 2 2
3 9 1
4 3 2

【输出样例】
1 4 -1 6

【算法代码】

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL cur;

int main() {
    int n;
    LL a,t,b;
    cin>>n;
    while(n--){
        cin>>a>>t>>b;
        if(a+b>=cur){
            cur=max(cur,a);
            cout<<cur<<" ";
            cur+=t;
        }
        else cout<<"-1 ";
    }

    return 0;
}

/*
in:
4
1 3 3
2 2 2
3 9 1
4 3 2

out:
1 4 -1 6
*/