CF1248E
题意
火车上有一行乘客,从左到右依次为1到n.在一号乘客的左侧有一个热水器,每个人都会在ti的时候想要去打水,每个人打水的时间都是p.打水需要排队.而且对于乘客i,如果在(1~i-1)范围内存在乘客正在排队,那么他就会等到前面的乘客都没在排队的时候,瞬间起身去排队.如果在一个瞬间有多个乘客想要起身,只有标号最小的乘客会排队,剩下的人会回到座位上等待下一时刻.
$1<=n<=1e6$
$1<=p,t_i<=1e9$
思路
最开始读题没看到排队这个设定,所以就一直wa.不过大体思路是对的.
我们定义三个队列.
第一个队列q,代表着他们初始时想要离开座位的顺序.是按照打水时间排序,小的在前.相同时间的话编号小的优先.
第二个是优先队列zero.表示他们已经可以随时起身排队,但是目前还不允许,所以zero按照编号递减排队,不在乎时间.
第三个是普通队列que,用以模拟正在排队的情况.
下面是分析过程
根据定义,可知q中的队列是按照时间递增的(然后以编号辅助排序),zero中的队列是按照编号递减的.
不难发现,由于每个人都不会在que中有比自己小的乘客的情况下排队,所以que一定是个根据编号递减的序列.也就是优先队列中的元素一定比que的队尾的编号大.
如果某一时刻(包括开始时刻),zero和que中都没有人,那么q的队首就会去排队,然后打水.
如果zero中有人,先尝试一下将zero的队首插入que的队尾,当然,根据性质,最多插入一个乘客.
在que的队首开始打水到结束打水的过程中,q中可能会出现几个想要打水的乘客.将时间上满足的乘客根据q中的顺序依次处理,如果这个乘客可以排队,那么就直接插入que,如果不能排队,就将其加入zero,等待时机.
总而言之,思路就是如何将q中的事件经由zero调整,一点一点插到que中.
AC代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define maxn (int)1e6 + 100
#define ll long long
struct Peo {
ll t;
int id;
bool operator<(const Peo& b) const { return id > b.id; }
Peo(ll _t, int _id) { t = _t, id = _id; }
Peo(){};
} a[maxn];
bool cmp(Peo& x, Peo& y) {
if (x.t == y.t)
return x.id < y.id;
return x.t < y.t;
}
ll ans[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
ll p;
cin >> n >> p;
for (int i = 0; i < n; ++i) {
cin >> a[i].t;
a[i].id = i;
}
sort(a, a + n, cmp);
queue<Peo> q, que;
for (int i = 0; i < n; ++i) {
q.push(a[i]);
}
priority_queue<Peo> zero;
ll pre = 0ll;
for (int i = 0; i < n; ++i) {
if (zero.empty()) {
// 如果优先队列和que都是空的,那么就跳过一部分时间,让q的队首去打水
if (que.empty()) {
pre = max(pre, q.front().t);
que.push(q.front());
q.pop();
}
} else {
// 队首接完水后,只要优先队列不空,那么就优先让优先队列的尝试排队(因为此时q中的都还没到喝水的时候)
while (que.empty() || zero.top().id < que.back().id) {
que.push(zero.top());
zero.pop();
}
}
int id = que.front().id;
// 队首在接水,此时考虑接水的过程中q序列中有人起身
while (!q.empty() && q.front().t <= pre + p) {
if (q.front().id < que.back().id) {
que.push(q.front());
q.pop();
} else {
zero.push(q.front());
q.pop();
}
}
// 队首接完水了,记录答案
que.pop();
ans[id] = pre + p;
pre = ans[id];
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
