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
*/