题解：CF1945G（Cook and Porridge）
题目翻译：
有 n n n 个人排队喝粥，对于第 i i i 个人，他有一个优先程度 k i k_i ki，并且喝一碗粥需要花费 s i s_i si 分钟。
供应粥的厨师总共工作 D D D 分钟，对于每一分钟，他会给排在队伍最前面的一个人打一碗粥，随后这个人离开队伍去喝粥。假设这个人是第 i i i 个人，并且此时是第 x x x 分钟，那么在第 x + s i x+s_i x+si 分钟这个人归队，队伍最后面所有优先程度严格小于他的人站在他后面，换句话说，这个人最终站的位置的后面所有的人的优先程度都小于他，这个人紧挨着的前面的一个人的优先程度大于等于他。
试问在
D
D
D 分钟内每个人能否都喝到粥？若可以，报告是在第几分钟；若不可以，输出 -1。
我们可以暴力的去枚举每一次操作，唯一的问题是如果我们按照题目的原要求去维护整个队伍，最终的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2) 的，无法通过。因此，我们考虑优化。我们不难发现，如果最初站队伍就是按照优先程度降序排列的，那么每一个时刻队伍都是按照优先程度降序排列的。因此，我们用一个数组记录最初排队的人（之后简称队列一），最前面的喝到了粥就把这个人对应的元素从开头删除，用另一个优先队列（之后简称队列二），比如 priority_queue，记录至少喝过一轮之后，重新进入队伍的人。枚举每一分，分别维护，即可求出答案。
具体的，我们需要定义一个结构体 {ys,wh,sm}，三个元素分别表示这个人的优先程度、进入队伍的时间以及喝一碗粥需要用到的时间。队列二的排序依据如下。第一关键字： ys 越大越好；第二关键字： wh 越小越好；第三关键字： sm 越小越好。之后维护一个对于元素 ys 的后缀最大值，也就是从某个点往后最大的一个优先程度。接下来枚举每一分钟，对于每一分钟，如果如果队列二为空或者它里面最好的一个的 ys 不如队列一种剩余的最大的一个 ys 大（这里用后缀最大值统计），我们就选择把队列一的第一个元素加入一个插入清单，并把它删除，否则就把队列二最好的元素加入清单，并把它删除。这里，它们的插入时间都是最初的 wh 加上对应的 sm。对于这个清单，我们根据它的出入时间为关键字进行排序，每次将插入时间为当前时间的插入到队列二中，并将这个信息从清单中删除。清单用 set 实现。
最后如果队列一被彻底清空了，答案就是它被清空的那一个时间，否则为 -1。
注意以下几点：
不要忘记判断 -1；
注意记录的是“它被清空的那一个时间”还是它被清空的下一个时间；
多则数据不能不清空。
最后的最后，代码走起！
#include<bits/stdc++.h>
#define N 220000
using namespace std;
int t,n,d,k[N],s[N];
struct Student{
int ys,wh,sm;
bool operator<(Student ot)const{
if(ys==ot.ys){
if(wh==ot.wh)return sm>ot.sm;
return wh>ot.wh;
}
return ys<ot.ys;
}
};
Student stu[N];
int maxh[N];
priority_queue<Student>bef;
set<pair<int,Student>>ps;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)scanf("%d%d",&k[i],&s[i]),stu[i]={k[i],-1,s[i]};
maxh[n]=stu[n].ys;
for(int i=n-1;i>=1;i--)maxh[i]=max(maxh[i+1],stu[i].ys);
while(bef.empty()==false)bef.pop();
ps.clear();
int tmp=0,i;
for(i=1;i<=d&&tmp+1<=n;i++){
if(bef.empty()==true||bef.top().ys<=maxh[tmp+1]){
tmp++;
ps.insert({i+stu[tmp].sm,{stu[tmp].ys,i+stu[tmp].sm,stu[tmp].sm}});
}else{
ps.insert({i+bef.top().sm,{bef.top().ys,i+bef.top().sm,bef.top().sm}});
bef.pop();
}
while(ps.empty()==false&&ps.begin()->first==i){
bef.push(ps.begin()->second);
ps.erase(ps.begin());
}
}
if(tmp==n)printf("%d\n",i-1);
else printf("-1\n");
}
return 0;
}
