这个问题的关键在于找到一个判定条件和 $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)$ 是一个单调递减函数。这种单调性通常暗示我们可以使用二分查找来求解。

排序 + 遍历

P3506.第1题-加权H指数

1000ms

Difficulty: 3

所属公司 : 阿里

算法与标签>贪心算法

题目内容

给定一个长度为 $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$ 指数。

输入

输出

输入

预期输出（选填）