www.luogu.com.cn

题目大意：

有一个队列，其中的每项工作 ii 都有两个值：最早可以处理的时间 tit_{i} 和处理所需要的时间 did_{i}，等待队列中的数量不可以超过 bb，求出每个工作完成时间（无法完成则输出 −1-1）。

模拟思路

这是一道结合了队列的模拟题，自然可以使用 queue\text{queue} 来做，但首先我们要搞清一下几点：

  • 如何判断当前时间点有多少件事情可以完成。

  • 如何根据队列中的等待数判断是否可以完成。

  • 如何计算下一个事情前的完成时间。

我们可以定义一个一维数组 bg[N]\text{bg[N]}，其中 bgibg_{i} 表示第 ii 个事情时最早的可以做的时间，而由于每个事情都有自己的最早可处理时间 tit_{i}，因此 max⁡(bgi−1,ti)\max(bg_{i - 1}, t_{i}) 即为第 ii 个事情的实际开始时间。显然可以得出转移方程：

bgi=max⁡(bgi−1+di−1,ti)bg_{i} = \max(bg_{i - 1} + d_{i-1},t_{i})

有因为一维数组 bgibg_{i} 的状态只和 bgi−1bg_{i - 1} 有关，所以我们可以直接使用一个变量来代替。

不多说了，看代码注释。

STL代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 不开long long见祖宗
const int N = 2e5 + 9;

queue<ll> q;
ll t[N], d[N];
ll bg_time, n, b;
int main()
{
    cin >> n >> b;
    for (int i = 1; i <= n; i++)
        cin >> t[i] >> d[i];
    for (int i = 1; i <= n; i++)
    {
        while (!q.empty() && q.front() <= t[i]) // 弹出或询问STL容器前一定要先判断容器是否为空！
            q.pop();
        if (q.size() <= b)
        {
            bg_time = max(bg_time, t[i]) + d[i]; // 相当于下一件事情的最早开始时间，也是本次结束时间。 
            cout << bg_time << ' ';
            q.push(bg_time); //将本次的可完成时间推入队列方便下次询问。
        }
        else
            cout << -1 << ' '; //其余的可能情况只能是无解的。
    }
    return 0;
}