自动搬运

查看原文

来自洛谷，原作者为

	yyyx_ 怎么还有条船不远万里。

搬运于2025-08-24 23:15:43，当前版本为作者最后更新于2025-05-10 21:49:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前情提要：多路归并优先队列（模板 P2085 最小函数值）。

题目简述：给定 $n$ 个二元组 $\{a_i,b_i\}$，选择编号为 $i$ 和 $j$ 的两个二元组（$i<j$），令 $S = \max(a_i,a_j) + \max(b_i,b_j)$，按 $S$ 为第一关键字，$p$ 为第二关键字，$q$ 为第三关键字从大到小排序得到排名前若干项。

$p$ 和 $q$ 的大小顺序很好处理，先考虑 $S$。将二元组按 $b_i$ 从大到小排序后设置 $n$ 个指针 $it_i$ 来表示 $a_i$ 下一个对应的 $b_{it_i}$。这样对于任意一个 $a_i$，$a_i + \max(b_i,b_{it_i})$ 的值是单调不增的。

用 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」落月摇情。

#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;
}