思路分析

核心思想：排序与贪心

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

排序 + 遍历

1. 排序：总时间复杂度是 $O(n \log R)$。考虑到 $R$ 可能达到 $10^9$，这个方法是可行的，但我们可以题目更深层的结构。我们关心的其实是当 $x$ 变化时，哪些论文被包含在。如果 $a_i$ 相同，排序顺序不影响结果。

2. 遍历与计算：$i$ 和权重 $w_i$ 作为一个二元组 $(a_i, w_i)$。然后将这 $n$ 个二元组按照引用次数 $a_i$ 从大到小进行排序排序后，我们得到一个新的序列 $(a'_1, w'_1), (a'_2, w'_2), ..., (a'_n, w'_n)$，其中 $a'_1 \ge a'_2 \ge ... \ge a'_n$。 我们从 $i=1$ 到 $n$ 遍历这个排好序的序列，并维护一个当前已遍历论文的权重累加和 current_weight_sum。 当遍历到第 $i$ 篇论文 $(a'_i, w'_i)$ 时：

   • current_weight_sum 表示的是引用次数排名前 $i$ 的论文的权重之和。

   • 这些论文的引用次数都大于等于 $a'_i$。

   • 对于任何一个潜在的H指数 $x \le a'_i$，这前 $i$ 篇论文都满足 $a'_j \ge x$ 的条件。因此，对于这样的 $x$，其权重和至少为 current_weight_sum。

   • 所以，在这一步，我们找到了一个满足条件的 $x$ 的集合。为了让 $x$ 尽可能大，它必须同时满足两个条件：

     1. $x \le a'_i$ (因为我们只考虑了引用次数至少为 $a'_i$ 的论文)
     2. $x \le$ current_weight_sum。

3. 最终答案：我们在整个遍历过程中，不断更新并记录所有候选答案中的最大值。遍历结束后，这个最大值就是我们要求的加权$H$指数。

C++

#include <iostream>
#include <vector>
#include <algorithm>

// 使用结构体存储每篇论文的引用次数和权重
struct Paper {
    long long a, w;
};

// 自定义比较函数，用于按引用次数降序排序
bool comparePapers(const Paper& p1, const Paper& p2) {
    return p1.a > p2.a;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<Paper> papers(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> papers[i].a;
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> papers[i].w;
    }

    // 按引用次数从大到小排序
    std::sort(papers.begin(), papers.end(), comparePapers);

    long long max_h = 0;
    long long current_weight_sum = 0;

    // 遍历排序后的论文
    for (int i = 0; i < n; ++i) {
        // 累加当前权重
        current_weight_sum += papers[i].w;
        // 计算当前候选的H指数
        // 候选值x需要满足 x <= a_i 和 x <= current_weight_sum
        // 我们取两者中的较小值，作为当前能达到的最大x
        long long candidate_h = std::min(papers[i].a, current_weight_sum);
        // 更新全局最大的H指数
        if (candidate_h > max_h) {
            max_h = candidate_h;
        }
    }

    std::cout << max_h << std::endl;
}

int main() {
    // 提高cin/cout效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Python

import sys

def solve():
    """
    处理单组测试数据的函数
    """
    try:
        # 从标准输入读取数据
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        a = list(map(int, sys.stdin.readline().split()))
        w = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    # 将论文的引用次数和权重打包成元组列表
    # papers[i] = (a_i, w_i)
    papers = list(zip(a, w))

    # 按引用次数 a_i 从大到小排序
    papers.sort(key=lambda x: x[0], reverse=True)

    max_h = 0
    current_weight_sum = 0

    # 遍历排序后的论文
    for citation, weight in papers:
        # 累加当前权重
        current_weight_sum += weight
        
        # 计算当前候选的H指数
        # 候选值x需要满足 x <= citation 和 x <= current_weight_sum
        # 我们取两者中的较小值，作为当前能达到的最大x
        candidate_h = min(citation, current_weight_sum)
        
        # 更新全局最大的H指数
        if candidate_h > max_h:
            max_h = candidate_h
            
    print(max_h)


def main():
    """
    主函数，处理多组测试数据
    """
    try:
        # 读取测试数据组数 T
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // 定义一个静态内部类来表示论文
    static class Paper {
        long a; // 引用次数
        long w; // 权重

        Paper(long a, long w) {
            this.a = a;
            this.w = w;
        }
    }

    // 处理单组测试数据的函数
    private static void solve(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        Paper[] papers = new Paper[n];
        
        // 读取引用次数
        StringTokenizer st_a = new StringTokenizer(br.readLine());
        // 读取权重
        StringTokenizer st_w = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            long a = Long.parseLong(st_a.nextToken());
            long w = Long.parseLong(st_w.nextToken());
            papers[i] = new Paper(a, w);
        }

        // 使用Lambda表达式按引用次数从大到小排序
        Arrays.sort(papers, (p1, p2) -> Long.compare(p2.a, p1.a));

        long maxH = 0;
        long currentWeightSum = 0;

        // 遍历排序后的论文
        for (int i = 0; i < n; i++) {
            // 累加当前权重
            currentWeightSum += papers[i].w;
            
            // 计算当前候选的H指数
            // 候选值x需要满足 x <= a_i 和 x <= currentWeightSum
            // 我们取两者中的较小值，作为当前能达到的最大x
            long candidateH = Math.min(papers[i].a, currentWeightSum);

            // 更新全局最大的H指数
            if (candidateH > maxH) {
                maxH = candidateH;
            }
        }

        System.out.println(maxH);
    }

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader以提高读取效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取测试数据组数 T
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            solve(br);
        }
    }
}

题目内容

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