魔法炼金术——三步炼成大挑战！

tag

模拟

题意简述

一个原材料需要经过三个步骤才能获得成品，为了方便我们这里把处理0次，1次，2次的数量记为 $f_1, f_2, f_3$，现在步骤一有 $n_1$ 台机器（即在同一时间最多同时处理 $n_1$ 个 $f_1$），每台步骤一的机器处理当前步骤需要 $t_1$ 个单位的时间。步骤二三同理，问要得到 $k$ 个成品，最少需要多少时间。

题解思路

我们可以考虑直接模拟，我们可以把每一个步骤的过程抽象成一个任务三元组 $(x，y，z)$，其中 $x$ 表示完成的时间点，$y$ 表示步骤的编号，$z$ 表示当前任务占用了多少台对应步骤的机器。我们用一个优先队列来维护当前的任务。对于一个任务，完成之后，我们可以得到 $z$ 个步骤 $y + 1$ 的产物，同时空出 $z$ 台可以用来生产 $y$ 的机器。此时我们可以检查步骤 $y + 1$ 的机器和 $y$ 的原料 $f_y$ 是否还有空余，如果有空余，我们可以继续加入新的任务。重复上述过程直到优先队列为空即可。最后的时间点就是答案。

部分细节在代码注释中体现。

参考代码

void solve()
{
    // n：每个步骤的机器的数量，t：每个步骤消耗的时间，f：每个步骤的原料数量，v：每个步骤空闲机器的数量
    array<int, 5> n, t, f, v;
    cin >> f[1];
    cin >> n[1] >> n[2] >> n[3];
    cin >> t[1] >> t[2] >> t[3];
    // 初始化
    int ans = 0;
    f[2] = 0, f[3] = 0;
    v[1] = n[1], v[2] = n[2], v[3] = n[3];
    // 任务三元组，first：完成的时间点，second：步骤的编号，third：当前任务占用了多少台对应步骤的机器
    priority_queue<piii, vector<piii>, greater<piii>> heap;
    // 最开始，处理步骤一，他会在t[1]时间后完成，占用n[1]台机器，使用min(n[1], f[1])个原料
    heap.push({ans + t[1], 1, min(n[1], f[1])});
    // 更新步骤一原料和空闲机器数量
    f[1] -= min(v[1], f[1]);
    v[1] -= min(v[1], f[1]);
    while(heap.size())
    {
        // 当前时间点，处理完成的步骤编号，当前步骤多出的空闲机器数量
        auto [now, id, cnt] = heap.top();
        // 更新答案
        ans = now;
        heap.pop();
        // 当前步骤完成后，会生成cnt个步骤id+1的原料，同时空出cnt台可以用来生产id的机器
        f[id + 1] += cnt;
        v[id] += cnt;
        // 检查步骤id+1的机器和id的原料f[id]是否还有空余，如果有空余，我们可以继续加入新的任务
        for(int i = 1; i <= 3; i ++)
            if(f[i] and v[i])
            {
                heap.push({now + t[i], i, min(f[i], v[i])});
                int tmp = min(f[i], v[i]);
                f[i] -= tmp;
                v[i] -= tmp;
            }
    }
    cout << ans << '\n';
}