CF1945G Cook and Porridge 题解
FFTotoro
·
·
题解
你需要的前置知识仅有结构体、重载运算符和 STL 的基本使用。
考虑模拟题目中的操作，建立两个队列 $Q_1$ 与 $Q_2$（前者是普通队列，使用 `std::vector` 模拟，存储开始时的所有学生；后者是优先队列，使用 `std::priority_queue` 模拟，表示后来插队进来的学生）。定义一个“学生”结构体，存储该学生的优先级 $k$、单次吃粥时间 $s$ 与进入 $Q_2$ 的时间 $t$（如果有），按照题目以 $k$ 为第一关键字（递减），$t$ 为第二关键字（递增），$s$ 为第三关键字（递增）。
可以使用一个指针扫 $Q_1$，如果该指针扫到尾了就代表所有学生都领到粥了。按照时间 $0,1,\ldots,D$ 依次模拟，考虑当前领到粥的是 $Q_1$ 中的人还是 $Q_2$ 中的人：如果 $Q_2$ 为空或者 $Q_2$ 中最大的 $k$ 不大于 $Q_1$ 中最大的 $k$，那么 $Q_2$ 没有人能直接插队到队首，$Q_1$ 的队头可以领一份粥；反之亦然。
接着考虑领到粥的人吃完粥的时间，在那个时间把他扔进 $Q_2$ 里面。
因为 $Q_1$ 是按顺序领粥的，所以求 $Q_1$ 中剩余的最大的 $k$ 只需维护原序列的 $k$ 的后缀最大值即可。
注意判断无解情况。
放代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Student{
int k,s,t;
Student(){t=0;}
Student(int k_,int s_,int t_){k=k_,s=s_,t=t_;}
bool operator <(const Student &x)const{
return k==x.k?t==x.t?s>x.s:t>x.t:k<x.k;
} // 注意 std::priority_queue 的排序规则是反着的
};
int main(){
ios::sync_with_stdio(false);
int t; cin>>t;
while(t--){
int n,d,p=0,w=-1; cin>>n>>d;
vector<Student> Q1(n);
for(auto &[k,s,t]:Q1)cin>>k>>s;
vector<int> s(n);
for(int i=n-1;~i;i--)
s[i]=max(i==n-1?0:s[i+1],Q1[i].k);
// 维护后缀最大值
priority_queue<Student> Q2;
vector<vector<Student> > v(d);
for(int i=0;i<d&&w<0;i++){
if(Q2.empty()||Q2.top().k<=s[p]){
if(int l=i+Q1[p].s;l<d)
v[l].emplace_back(Q1[p]);
if(++p==n)w=i+1; // 所有人都吃了
} // 从 Q1 队头拿人
else{
if(int l=i+Q2.top().s;l<d)
v[l].emplace_back(Q2.top());
Q2.pop();
} // 从 Q2 队头拿人
for(auto [k,s,t]:v[i])
Q2.emplace(k,s,i);
// 把吃完粥的人扔进 Q2
}
cout<<w<<'\n';
}
return 0;
}
```