题目链接：CF1239C Queue in the Train
题目标题
火车上的队列
题意简述
火车上有一排座位，标号 1..n 。座位上的每个人需要去接开水烧方便面（题目这么说的）。每个人接开水都一致地需要 p 分钟，而走动的时间可忽略不计。第 i 个人从第 t_i 分钟开始，就会打算去接开水。
同一时刻只能有一人在接水，因此，自然会出现排队的情况。
然而人们都不想排队。第 i 个人会关注第 1 到 i-1 个座位（如果这些座位是空的，那么座位上的人肯定是在接水或者排队）。即，第 i 个人会在第 t_i 分钟后的，(第 1 到第 i-1 个座位都不是空的)的最早时间离开座位，去接水或者排队。
另外，还有一个潜规则：如果在同一时刻，有多个人可以离开座位，那么只有坐在编号最小的座位上的人会离开座位，其他的则继续等待。
现在，你需要计算每个人接完水的时刻。
解题思路
这题题目中存在很多要维护的东西，比如，正在等待的人的集合、队列中的人的集合（包括正在接水的那个），以及当前时间。如果使用普通的模拟做法，则较为难写。如果将时间离散化，按照时刻处理，同样非常难处理。
那么，我们可以使用“事件化”的办法进行模拟。
此处定义“事件”是一个三元组 (time,type,id) 。其中， time 表示事件发生的时间， type 表示事件类型（0 表示接水完成，离开接水的队列；1 表示开始等待）， id 则表示事件的对象（即，受影响的人的编号）。
一开始，有 n 个事件，即，对于所有 1 \leq i \leq n 的 (t_i,1,i)。我们将这 n 个事件放入事件队列。
我们还需要维护以下内容：
- wait ，表示当前正在等待的人的集合（这些人还在座位上）。维护的数据结构需要支持以下操作（因此选择使用优先队列）：
- 取出最小值。对于任何等待队列中的人可以进入接水队列的情景，一定是最小值优先。
- 删除最小值。当一个人进入了接水队列，就不再属于等待队列。
- 插入值。当处理到 type = 1 的事件时，对应的人要进入等待队列。
- q ，表示当前接水队列中的人的集合（包括正在排队和正在接水的）。需要支持以下操作（因此选择使用set）：
- 删除指定值。当处理 type = 0 的事件时，需要将指定的值从队列中移除
- 取出最小值。如果等待队列中编号最小的人编号比接水队列中的最小编号还要小，这个人才能进入接水队列。
- 插入值。如果等待队列中编号最小的人编号比接水队列中的最小编号还要小，这个人就要进入接水队列。
- currtime ，当前正在处理的事件发生的时间。
- emptytime 。在不会再有人进入接水队列的情况下，预计接水队列将会为空的时刻。或者说，最后一个进入接水队列的人完成接水的时刻。
随后，我们从事件队列中取出最早发生的事件，并将其删除（我们认为，type = 0 的事件总是在 type = 1 的事件之前进行（原因见下文），并且，对于 type = 1 的事件，id 小的先进行）。随后，我们对这个事件进行处理。
- 如果 type = 0，那么直接从接水队列中将对应的人删除
- 如果 type = 1，那么将指定的人加入等待队列
在处理完一个事件后，要么是接水队列改变，要么是等待队列改变。这些改变可能会引起当前等待队列中编号最小的人编号比接水队列中的最小编号还要小。那么，这时候，等待队列中编号最小的人就需要进入接水队列。这个人进去之后，等待队列的最小编号必定要大于接水队列的最小编号，因此无需继续判断。
一个人t从等待队列进入接水队列后，显然，他完成接水的时刻是 max(currtime,emptytime) + p 。因此，我们要添加一个事件 (max(currtime,emptytime) + p,0,t) ，然后将 emptytime 更新为 max(currtime,emptytime) + p 。此时，我们就可以进行答案的统计，因为我们知道了编号为t的人接水结束的时间。
因此只要反复处理事件，直到事件队列为空，我们就求得了所有答案。
总结
问题：为什么要使用上文提到的，对事件的排序方式呢？
如果 type = 1 的操作先于 type = 0 的执行，你会发现，你愉快地被样例叉掉了。因为，如果先执行 type = 1 ，那么在判断等待队列中的人是否能进入接水队列时，原本已经接水完成，要离开接水队列的人却没有即使离开，会导致影响判断。而如果在 type = 1 时，id 大的先执行，则会违反题目中提到的“潜规则”。
总结：本题中，进入等待队列和离开接水队列的事件有着共同之处，那就是，①必须按照时间顺序交替处理，②处理完毕后，都必须检查等待队列的人能否进入接水队列。另外，我们需要求接水队列的最小值。如果使用队列std::queue处理，则相当麻烦，而使用事件化的方式处理离开接水队列的事件，则完美地避免了使用队列，方便了最小值的统计。
代码
// status: [Accepted][unofficial]
// oj: [Codeforces]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 100005;
int n,tt;
int t[MAXN];
int ans[MAXN];
// 事件
struct Event {
int time; // 发生时间
int type; // 类型
int id; // 影响到的人
Event() {}
Event(int _time,int _type,int _id) {time=_time;type=_type;id=_id;}
bool operator<(const Event &other) const {
if(time != other.time) return time > other.time; // 此处的排序必须反过来，因为优先队列是从大到小排列的。
if(type != other.type) return type < other.type;
return id > other.id;
}
};
// 事件队列
priority_queue<Event> ev;
// 接水队列
set<int> q;
// 等待队列。使用模板 greater<int>，以使得编号小的人先被取出。
priority_queue<int,vector<int>,greater<int> > wait;
signed main() {
ios::sync_with_stdio(false);
cin>>n>>tt;
for(int i=1;i<=n;i++) {
cin>>t[i];
// 创建一开始的n个事件
ev.push(Event(t[i],true,i));
}
int currtime = 0;
int emptytime = 0;
while(!ev.empty()) {
Event c = ev.top(); ev.pop();
currtime = c.time;
if(c.type == 0) {
// cerr<<currtime<<": "<<c.id<<" left the queue."<<endl;
q.erase(c.id);
}
else {
// cerr<<currtime<<": "<<c.id<<" became waiting."<<endl;
wait.push(c.id);
}
// 这是等待队列中的人进入接水队列的条件
while(!wait.empty() && (q.empty() || wait.top() < *q.begin())) {
int p = wait.top();wait.pop();
// cerr<<currtime<<": "<<p<<" entered the queue."<<endl;
q.insert(p);
// 计算这个人接水完毕的时刻
int et = max(currtime, emptytime) + tt;
// 创建这个人离开接水队列的事件
ev.push(Event(et,false,p));
// 更新emptytime
emptytime = et;
// 统计答案
ans[p] = et;
}
}
for(int i=1;i<=n;i++) {
if(i>1) cout<<' ';
cout<<ans[i];
}
cout<<endl;
}
评测记录：R25487378
Comments | NOTHING