E - Set Meal
2huk
·
·
个人记录
Description
给定 n 个数 a_i 和 m 个数 b_i。再给定 q 个关键对 (c_i, d_i)。请你找到一个非关键对 (x_i, y_i)，使得 a_{x_i} + b_{y_i} 最大。求最大的 a_{x_i} + b_{y_i}。
## Solution
首先将 $b$ 从大到小排序，然后统计对于每个 $a_i$ 而言，那些 $b_j$ 与它构成关键对。这里可以用 $\text {vector}$ 存储。
然后我们枚举 $a_i$，现在我们想找到一个位置 $j$，使得 $(i, j)$ 不为关键对且 $b_j$ 最大。因为我们已经将 $b$ 从大到小 排序了，所以只需要找到最小的 $j$ 即可。
又因为我们在前面统计了每个与 $i$ 有关的关键对，不妨令其为 $v_i$（这是一个 $\text {vector}$），那么实际上就是要找到最小的不在 $v_i$ 中出现的数。这本质上就是从 $1$ 开始的 $\operatorname{mex}$ 值。
我们可以直接暴力去求它。比如对于这样一个 $v_i$ 而言：
$$
v_i = \{1, 2, 3, 5, 6, \dots\}
$$
可以发现这个 $v_i$ 已经从小到大排序了。其中 $v_{i, 3}$ 的值为 $3$，那么就代表 $1, 2, 3$ 一定都出现过。可是 $v_{i, 4}$ 的值并不为 $4$，也就是说在这个 $v_i$ 中 $4$ 没有出现过。因为我们是从小到大枚举的，所以 $4$ 就是这个序列的伪 $\operatorname{mex}$ 值。
因此我们首先要对每个 $v_i$ 中的元素从小到大排序，然后暴力求解即可。可以发现这样暴力计算的复杂度为 $\Theta\left(\sum \text{size of }(v_i)\right) = \Theta (q)$。
## Code
```cpp
int n, m, q, a[N];
PII b[N];
int now[N];
vector<int> v[N];
int res;
signed main()
{
n = read(), m = read(), q = read();
fup (i, 1, n) a[i] = read();
fup (i, 1, m) b[i] = {read(), i};
sort(b + 1, b + m + 1, [&](PII x, PII y)
{
return x.fi > y.fi;
});
fup (i, 1, m) now[b[i].se] = i;
fup (i, 1, q)
{
int x = read(), y = read();
v[x].push_back(y);
}
fup (i, 1, n)
{
for (auto &j : v[i]) j = now[j];
sort(v[i].begin(), v[i].end());
}
fup (i, 1, n)
{
int j = 0;
for (; j < v[i].size(); ++ j )
if (v[i][j] != j + 1)
break;
++ j;
res = Max(res, a[i] + b[j].fi);
}
wel(res);
return 0;
}
```