题解：P12459 [JOI2025 预选赛 R2] 亲密的厨师
yyyx_
·
·
题解
前情提要：多路归并优先队列（模板 P2085 最小函数值）。
题目简述：给定 n 个二元组 \{a_i,b_i\}，选择编号为 i 和 j 的两个二元组（i<j），令 S = \max(a_i,a_j) + \max(b_i,b_j)，按 S 为第一关键字，p 为第二关键字，q 为第三关键字从大到小排序得到排名前若干项。
用 set 存一下对于每个人不能合作的人的编号，指针遍历查找下一个的时候在 set 里查一下有没有 $it_i$ 就行了。注意我们实际钦定了 $a_i$ 的大小关系，所以若 $a_i<a_{it_i}$ 是不能放进优先队列的。若找到合法搭配，将多元组 $\{a_i + \max(b_i,b_{it_i}),\min(i,it_i),\max(i,it_i)\}$ 加入队列即可。
注意上述做法会出现重复，所以任意钦定一下顺序，当加入队列的两人组编号 $i,it_i$ 中 $i>it_i$ 时才加入队列。
时间复杂度 $O(n\log n)$。
同做法好题：[P10768 「CROI·R2」落月摇情](https://www.luogu.com.cn/problem/P10768)。
```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x)
{
x = 0;
char c = getchar();
bool f = false;
while (c < '0' || c > '9')
{
if (c == '-')
f = true;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
f ? (x = -x) : 0;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...temps)
{
read(x), read(temps...);
}
#define de(x) cerr << '[' << #x << ' ' << '=' << ' ' << x << ']' << ' '
#define ed() cerr << endl
const int N = 4e5 + 5;
typedef long long ll;
struct node
{
int v1, v2, id;
} a[N];
int n, m, q;
set<int> st[N];
int it[N], to[N];
int ans[N];
priority_queue<tuple<int, int, int, int>> Q;
void insert(int id)
{
int &i = it[id];
++i;
for (; i <= n; i++)
{
int j = a[i].id;
if (st[id].count(j))
continue;
j = to[j];
int k = to[id];
if (a[k].v1 < a[j].v1)
continue;
if (a[k].v1 == a[j].v1 && a[k].id <= a[j].id)
continue;
Q.emplace(a[k].v1 + max(a[k].v2, a[j].v2), min(id, a[i].id), max(id, a[i].id), id);
return;
}
}
signed main()
{
read(n, m, q);
for (int i = 1; i <= n; i++)
read(a[i].v1), a[i].id = i;
for (int i = 1; i <= n; i++)
read(a[i].v2), st[i].emplace(i);
for (int i = 1, x, y; i <= m; i++)
{
read(x, y);
st[x].emplace(y);
st[y].emplace(x);
}
sort(a + 1, a + n + 1, [](node x, node y)
{ return x.v2 == y.v2 ? x.id > y.id : x.v2 > y.v2; });
for (int i = 1; i <= n; i++)
to[a[i].id] = i;
for (int i = 1; i <= n; i++)
insert(i);
vector<int> qy;
for (int x; q--;)
{
read(x);
qy.emplace_back(x);
}
int M = *max_element(begin(qy), end(qy));
for (int i = 1; i <= M; i++)
{
auto [v, id1, id0, id] = Q.top();
Q.pop();
ans[i] = v;
insert(id);
}
for (auto x : qy)
printf("%d\n", ans[x]);
return 0;
}
```