题解：CF1945G（Cook and Porridge）

题解：CF1945G（Cook and Porridge）

题目翻译：

有 $n$ 个人排队喝粥，对于第 $i$ 个人，他有一个优先程度 $k_i$，并且喝一碗粥需要花费 $s_i$ 分钟。

供应粥的厨师总共工作 $D$ 分钟，对于每一分钟，他会给排在队伍最前面的一个人打一碗粥，随后这个人离开队伍去喝粥。假设这个人是第 $i$ 个人，并且此时是第 $x$ 分钟，那么在第 $x+s_i$ 分钟这个人归队，队伍最后面所有优先程度严格小于他的人站在他后面，换句话说，这个人最终站的位置的后面所有的人的优先程度都小于他，这个人紧挨着的前面的一个人的优先程度大于等于他。

试问在 $D$ 分钟内每个人能否都喝到粥？若可以，报告是在第几分钟；若不可以，输出 -1。

我们可以暴力的去枚举每一次操作，唯一的问题是如果我们按照题目的原要求去维护整个队伍，最终的时间复杂度是 $O(n^2)$ 的，无法通过。因此，我们考虑优化。我们不难发现，如果最初站队伍就是按照优先程度降序排列的，那么每一个时刻队伍都是按照优先程度降序排列的。因此，我们用一个数组记录最初排队的人（之后简称队列一），最前面的喝到了粥就把这个人对应的元素从开头删除，用另一个优先队列（之后简称队列二），比如 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;
}