参考题解

用队列存储等待进入餐厅的顾客组（按到达顺序），用小根堆记录餐厅内顾客的离开时间和人数（便于快速获取最早离开的组）；处理每组顾客时，先移除堆中已离开的组并更新当前餐厅人数，再将新到组加入等待队列，随后循环尝试让队首组进入餐厅 —— 若当前时间（取组到达时间和餐厅可容纳的最早时间的最大值）下餐厅剩余容量足够，则记录进入时间并将该组加入堆，否则等待最早离开的组离开后再重试，最终高效计算出每组进入餐厅的时间，时间复杂度为 O (N log N)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;

struct node  // 存储每组顾客的信息
{
    int a , b , c;  // a：到达队列的时间；b：在餐厅停留的时间；c：该组人数
};

void solve()
{
    int n, k;
    cin >> n >> k;  // 输入顾客组数n和餐厅最大容量k
    vector<node> vec(n + 1);  // 用1-based数组存储所有组的信息
    for (int i = 1; i <= n; i++) cin >> vec[i].a >> vec[i].b >> vec[i].c;

    vector<int> ans(n + 1);  // 存储每组进入餐厅的时间

    // 小根堆：存储餐厅内顾客的离开时间和人数（按离开时间升序）
    priority_queue<PII, vector<PII>, greater<PII> > heap;

    queue<int> q;  // 模拟等待队列，存储等待的顾客组编号

    int cur = 0;  // 当前餐厅内的总人数
    int now = 0;  // 当前时间点        

    for (int i = 1; i <= n; i++ )  // 按到达顺序处理每组顾客
    {
        // 处理在第i组到达前已经离开餐厅的顾客（更新当前人数）
        while (heap.size() && heap.top().first <= vec[i].a) 
        {
            cur -= heap.top().second;  // 减去离开的人数
            heap.pop();
        }

        q.push(i);  // 将当前组加入等待队列

        // 尝试让等待队列中的组进入餐厅
        while (q.size()) 
        {
            int id = q.front();  // 取队首组

            // 确定当前可处理的最早时间（不早于该组到达时间）
            now = max(now, vec[id].a);

            // 处理在当前时间点前已经离开餐厅的顾客
            while (heap.size() && heap.top().first <= now) 
            {
                cur -= heap.top().second;
                heap.pop();
            }

            // 若当前组进入后不超过餐厅容量
            if (cur + vec[id].c <= k)
             {
                ans[id] = now;  // 记录进入时间
                cur += vec[id].c;  // 更新餐厅内人数
                heap.push({now + vec[id].b, vec[id].c});  // 记录该组离开时间和人数
                q.pop();  // 从等待队列移除
            } 
            else 
            {
                // 容量不足，等待最早离开的组离开后再尝试
                now = heap.top().first;
            }
        }
    }

    // 输出每组进入餐厅的时间
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;

    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}