思路分析

核心思想：排序与贪心

这个问题的关键在于找到一个判定条件和 $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$ 。