Nowcoder girl 2019：第四题 泡面

题目链接🔗:泡面

题意简述

先把题目抽象：现在（ ）有一个含 个元素的数组，存的是它的入队时间 ,一旦发现到了入队时间，就得加入一个以编号排序的优先队列，每次消灭一个队头， 就会刷新成 。

解题思路

这题不需要太多的思考，考的是纯数据结构，只要按照题意，维护这样的优先队列即可。
 
那么对于一个像我一样的小菜鸡，读懂题意之后，依次需要解决哪些问题呢？

数据的存储

• 用 priority_queue<int,vector<int>,greater<int>> 来储存座位编号，解决打水队列的优先顺序问题。

• 由于打水结束时间和座位 的顺序是不同的，题目要求按照 顺序输出打完水的时间，所以要额外开一个数组 ans[id] ，以 映射到打水结束时间，最后统一输出。

• 记录观察起始时间 的数组 a[N] 需要进行从小到大的排序来简化后续的搜寻时间，因此初始的 会遗失掉，怎么让 跟着自己的 跑呢？
  开一个 pair<int,int> 是很好的选择，pair 默认按照 pair.first 排序，在 pair.first 相同的情况下，按照 pair.second 排序。所以，我们把 存在 pair.first 中， 存在 pair.second 中就能完美解决这个问题。（开结构体也是可以的，不过需要自己重新写一下排序规则=v=个人觉得比 pair 麻烦。）

维护结构

解决了数据的存储问题之后，接下来的问题就是，如何用循环来维护这个动态平衡？

• 每个 肯定都要被扫描一遍是否符合打水时间，所以外层循环考虑用 for 循环把每个 依次在符合条件的情况下加入打水队列。

• 循环内部就比较自由了，只要能做到以下几点皆可：

  1. 在打水队列打水并更新 的过程中，一旦发现有 ,立刻加入打水队列，并且立刻转移到关注 是否加入打水队列。
  2. 在没人想加入打水队列的情况下，打水队列默默打水，直到 满足 的要求。
  3. 打水队列打空之后，如果还有人坐在位子上没有打水， ，我们就时空穿越，把 更新成当时扫描到的 ，也就是当前没打水的人里最早想打水的那位，把他加入打水队列开始打水。
  4. 把每个 都加入打水队列之后，我们就退出这个循环了。不要忘记让还在队列里的人把水打完，最后要加个独立的 while 循环来清空队列。

代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
pair<int, int> a[N];//储存打水人的打水时间和编号
long long ans[N];//储存每个人的最终打水时间

int main()
{
    int n, p;
    cin >> n >> p;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a, a + n);//将开始观察时间t从小到大排序

    long long cur = 0;// current time 维护打水时间，就是题解中说的now
    priority_queue<int,vector<int>,greater<int>> water;//打水队列
    for (int i = 0; i < n; ++i) {
        while (!water.empty() && cur < a[i].first) {//如果打水队列不空，而且还没到指针的人的打水时间
            auto id = water.top();//取出队头,让它去打水
            water.pop();
            cur += p;//打水时间更新
            ans[id] = cur;//记录这个人打完水的时间
        }
        water.push(a[i].second);//如果指针指到的人也想打水了，就加入打水队列
        if (cur < a[i].first) cur = a[i].first;//队列空的话就让指针的那个人去打水
        //打水时间是他开始观察的时间+p
    }

    //for循环结束后现在所有人要么打完水了，要么在打水队列里
    while (!water.empty()) {//同上，没打完的继续按照顺序打水，存下打完水的时间，直到所有人打完水
        auto id = water.top();
        water.pop();
        cur += p;
        ans[id] = cur;
    }

    //输出每个人的打水时间
    for (int i = 0; i < n; ++i)cout << ans[i] << " ";
    return 0;
}