前言

2025/9/16 我不知道自己选择的道路是否正确

继ABC420写出来6题之后，我接连两次只写出来3题——一次是题目是在太狗屎，一次是我太自大太懒惰加上有点心事了。
ABC423，做出来4题——不是ABCD，而是ABCE，那么D题呢？
我是小丑，读错题+忘记优先队列默认是大根堆了，嘿嘿嘿。

题目大意

原题

DeepL翻译（我自己读的时候有点坑）

有一家餐厅最多可同时接待 $K$ 位顾客。餐厅前面有一条小路，小路上有一条排队通道。

在时间 $0$ 时，餐厅内没有顾客，排队队伍也是空的。

今天，有 $N$ 组顾客预定前来就餐，他们按照到达的先后顺序被编号为从 $1$ 到 $N$ 。 $i$ 组由 $C_i$ 人组成，在 $A_i$ 时进入队列末尾，并在进入餐厅后的 $B_i$ 个时间单位离开餐厅。

每个群体都是在同时满足以下两个条件的最早时间离开队列进入餐厅的：

  • 该组位于队列前列。换句话说，该组是当时仍在排队的人中最早加入的一组。
  • 将该组人数与餐厅内所有当前排队的人数(包括在该时间段进入餐厅的人数，不包括离开餐厅的人数)相加，人数为 $K$ 或更少。

求每组人进入餐厅的时间。

自己读题去吧，这题难点就是读懂题目。除此之外没啥难的，纯粹是我脑子不好。

分析

我好像做过类似的题，但好像又没什么印象，所以对我来说算是模拟题。
首先，想到暴力的方法——枚举每时每刻，但 $A,B\leq10^7$ 所以不太行。
（不对啊我靠，不会 1e7 可以吧？啊？我又想复杂了。没事，我这个方法无论 $A,B$ 的大小。）

但并不是每个时间都是有用的，就像身边的人一样。我曾幻想与每个人交好，现在看来只留一些有价值的即可。
显然，有价值的点就是每组顾客进出的时间——只有 $2N$，可以接受。
那我们就开一个存事件的优先队列，先把每一组顾客进队放进优先队列中（记得默认是大根堆！！！），按时间取出来。接下来分类讨论进队和出餐厅的操作：

  • 对于入队操作
    • 如果当前餐厅容得下你，就放进去，并且将出餐厅的操作（是 $time+b_{id}$ ！）加入到事件中。你进餐厅的时间就是入队时间。
    • 容不下你的话，维护一个队列排队，然后你进去等着别人来处理吧。
  • 对于出餐厅的操作，直接将当前餐厅人数减掉。由于人数变少了，有的排队的人也该进来了，那就一直让排队的人进来，直到塞不下了。那每一个出队的进餐厅的时间就是当前的时间，并且再把这一组顾客出餐厅加入事件中。

然后就没了，真的没什么难的。
我真的是傻子。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,k,a[N],b[N],c[N],ans[N],sum;
struct node{
    int type,time,id; 
    bool operator <(const node&w)const{return time>w.time;}//默认大根堆！！！
}; 
priority_queue<node> mk; 
queue<int> q;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        mk.push({0,a[i],i});
    } 
    while(!mk.empty()){
        int type=mk.top().type,time=mk.top().time,id=mk.top().id;
        mk.pop();
        if(type){
            sum-=c[id];
            while(!q.empty()&&sum+c[q.front()]<=k){
                int i=q.front();
                sum+=c[i],ans[i]=time,mk.push({1,time+b[i],i});
                q.pop();
            } 
            continue;
        }
        if(sum+c[id]<=k&&q.empty()) sum+=c[id],ans[id]=time,mk.push({1,time+b[id],id});
        else q.push(id);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}