思路分析

核心思想：排序与贪心

这个问题的关键在于找到一个判定条件和 $x$ 之间的关系。让我们定义一个函数 $f(x) = (\sum_{i \text{ s.t. } a\_i \ge x} w_i) - x$。我们就是要找使得 $f(x) \ge 0$ 成立的最大的 $x$。

可以观察到，随着 $x$ 的增大，满足条件 $a_i \ge x$ 的论文数量会减少或不变，因此这些论文的权重之和 $\sum w_i$ 是一个非增函数。而 $x$ 本身是严格递增的。所以，$f(x)$ 是一个单调递减函数。这种单调性通常暗示我们可以使用二分查找来求解。

排序 + 遍历

题目内容

给定一个长度为 $n$ 的非负整数序列 {$a_1,a_2,...,a_n$} 以及对应的非负整数权重序列 {$w_1,w_2,...,w_n$}。

其中，第 $i$ 篇论文被引用 $a_i$ 次，具有权重 $w_i$ 。

定义“加权 $H$ 指数"为最大的非负整数 $x$ ，使得在所有被引用次数至少 $x$ 的论文中，它们的权重之和至少为 $x$ 。

请你计算并输出该加权 $H$ 指数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n(1 ≤n≤2×10^5)$ ，表示论文数量；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(0 ≤ a_i≤ 10^9)$，其中 $a_i$ 表示第 $i$ 篇论文的引用次数；

第三行输入 $n$ 个整数 $w_1,w_2,...,w_n(0 ≤ w_i ≤ 10^9)$ 其中 $w_i$ 表示第 $i$ 篇论文的权重。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

每组测试数据输出一行一个整数，表示加权 $H$ 指数。

样例1

输入

1
5
5 3 1 4 2
1 2 1 3 2

输出

4