Codeforces #594 div1 C/div2 E – Queue in the Train

题目链接：https://codeforces.com/contest/1239/problem/C

题意：火车上有n位乘客，按照1到n编号，编号为i的人会在ti分钟想去打水。水箱只能供一位乘客使用，每位乘客会使用p分钟。当一位乘客想要去打水时，他会先看编号在他前面的乘客是不是都在座位上，如果有人没在座位上，他会坐下继续等待，否则他会去排队打水。当某一时刻有几位乘客同时想要打水时，编号最小的乘客会前去打水，其他人会坐下继续等待，计算每位乘客打完水的时间。

做法：模拟。。首先我们需要一个优先队列判断座位上的人谁先去打水，然后我们需要一个优先队列判断坐在座位上等待的人，接着我们需要一个队列模拟正在排队的人，最后我们需要一个数据结构记录空的座位。按照题意模拟即可，具体实现见代码。

参考代码：

#include <iostream>
#include <queue>
#include <set>

using namespace std;
struct passenger
{
    int pos, startime;
} psger[100005];

struct cmp_waiting
{
    bool operator()(const passenger &x, const passenger &y)
    {
        return x.pos > y.pos;
    }
};

struct cmp_sitting
{
    bool operator()(const passenger &x, const passenger &y)
    {
        if (x.startime == y.startime)
            return x.pos > y.pos;
        else
            return x.startime > y.startime;
    }
};

priority_queue<passenger, vector<passenger>, cmp_sitting> sitting;
priority_queue<passenger, vector<passenger>, cmp_waiting> waiting;
queue<passenger> queuing;
set<int> emptyseat;
long long ret[100005];

int main()
{
    int n;
    long long p, now;
    cin >> n >> p;
    for (int i = 1; i <= n; ++i)
    {
        cin >> psger[i].startime;
        psger[i].pos = i;
        sitting.push(psger[i]);
    }
    now = sitting.top().startime;
    emptyseat.insert(n + 1);
    while (!sitting.empty() || !queuing.empty() || !waiting.empty())
    {
        if (!queuing.empty())
        {
            passenger fir = queuing.front();
            queuing.pop();
            now += p;
            ret[fir.pos] = now;
            while (!sitting.empty() && sitting.top().startime <= now)
            {
                passenger sec = sitting.top();
                if (sec.pos < *emptyseat.begin())
                {
                    emptyseat.insert(sec.pos);
                    queuing.push(sec);
                }
                else
                    waiting.push(sec);
                sitting.pop();
            }
            emptyseat.erase(fir.pos);
        }
        if (queuing.empty() && waiting.empty())
            now = max(now, (long long) sitting.top().startime);
        while (!sitting.empty() && sitting.top().startime <= now)
        {
            waiting.push(sitting.top());
            sitting.pop();
        }
        int id = *emptyseat.begin();
        if (!waiting.empty() && waiting.top().pos < id)
        {
            queuing.push(waiting.top());
            emptyseat.insert(waiting.top().pos);
            waiting.pop();
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << ret[i] << " ";
    return 0;
}