淘天笔试 淘天笔试题 0830
笔试时间：2025年8月30日
往年笔试合集：
第一题
给定一个长度为n的非负整数序列{a₁,a₂,…,aₙ}以及对应的非负整数权重序列{w₁,w₂,…,wₙ}。
其中，第i篇论文被引用aᵢ次，具有权重wᵢ。
定义“加权H指数”为最大的非负整数x，使得在所有被引用次数至少x的论文中，它们的权重之和至少为x。
请你计算并输出该加权H指数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1 ≤ T ≤ 10⁴)代表数据组数，每组测试数据描述如下：
第一行输入一个整数n(1 ≤ n ≤ 2×10⁵)，表示论文数量；
第二行输入n个整数a₁,a₂,…,aₙ(0 ≤ aᵢ ≤ 10⁹)，其中aᵢ表示第i篇论文的引用次数；
第三行输入n个整数w₁,w₂,…,wₙ(0 ≤ wᵢ ≤ 10⁹)，其中wᵢ表示第i篇论文的权重。
除此之外，保证单个测试文件的n和不超过2×10⁵。
输出描述
每组测试数据输出一行一个整数，表示加权H指数。
样例输入
1
5
53142
12132
样例输出
4
为了解决这个问题，我们需要计算给定论文集合的加权H指数。加权H指数定义为最大的非负整数x，使得所有被引用次数至少为x的论文的权重之和至少为x。
参考题解
问题分析：我们需要找到最大的x，使得满足条件的论文的权重之和至少为x。关键在于如何高效地计算这个x，而不是暴力枚举所有可能的x值。关键观察：x的取值范围受限于最大引用次数和总权重之和。x必须同时不超过最大引用次数和总权重之和。算法选择：排序：将论文按引用次数升序排序，以便快速筛选满足条件的论文。后缀和数组：预处理权重之和的后缀数组，以便快速计算从任意位置到末尾的权重和。二分查找：在可能的x范围内进行二分查找，检查每个中间值是否满足条件，从而高效地确定最大的x。
C++：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n == 0) {
cout << 0 << '\n';
continue;
}
vector<int> a_list(n), w_list(n);
for (int i = 0; i < n; ++i) {
cin >> a_list[i];
}
for (int i = 0; i < n; ++i) {
cin >> w_list[i];
}
// 组合并按a值排序
vector<pair<int, int>> papers(n);
for (int i = 0; i < n; ++i) {
papers[i] = {a_list[i], w_list[i]};
}
sort(papers.begin(), papers.end());
// 提取排序后的a和w
vector<int> a_sorted(n), w_sorted(n);
for (int i = 0; i < n; ++i) {
a_sorted[i] = papers[i].first;
w_sorted[i] = papers[i].second;
}
// 计算后缀和
vector<long long> suffix_sum(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
suffix_sum[i] = suffix_sum[i + 1] + w_sorted[i];
}
// 确定二分查找边界
int max_a = a_sorted.back();
long long total_weight = suffix_sum[0];
int high_bound = min(max_a, (int)total_weight) + 1;
// 二分查找
int low = 0, high = high_bound;
while (low < high) {
int mid = (low + high) / 2;
// 找到第一个大于等于mid的位置
auto it = lower_bound(a_sorted.begin(), a_sorted.end(), mid);
int idx = it - a_sorted.begin();
long long total_w = suffix_sum[idx];
if (total_w >= mid) {
low = mid + 1;
} else {
high = mid;
}
}
cout << low - 1 << '\n';
}
return 0;
}
Java：
import java.util.*;
import java.io.*;
public class MaxValidValue {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
int n = Integer.parseInt(br.readLine());
if (n == 0) {
System.out.println(0);
continue;
}
int[] aList = new int[n];
int[] wList = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
aList[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
wList[i] = Integer.parseInt(st.nextToken());
}
// 组合并按a值排序
int[][] papers = new int[n][2];
for (int i = 0; i < n; i++) {
papers[i][0] = aList[i];
papers[i][1] = wList[i];
}
// 按a值升序排序
Arrays.sort(papers, Comparator.comparingInt(p -> p[0]));
// 提取排序后的a和w
int[] aSorted = new int[n];
int[] wSorted = new int[n];
for (int i = 0; i < n; i++) {
aSorted[i] = papers[i][0];
wSorted[i] = papers[i][1];
}
// 计算后缀和
long[] suffixSum = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
suffixSum[i] = suffixSum[i + 1] + wSorted[i];
}
// 确定二分查找边界
int maxA = aSorted[n - 1];
long totalWeight = suffixSum[0];
int highBound = Math.min(maxA, (int)totalWeight) + 1;
// 二分查找
int low = 0, high = highBound;
while (low < high) {
int mid = (low + high) / 2;
// 找到第一个大于等于mid的位置（模拟bisect_left）
int idx = bisectLeft(aSorted, mid);
long totalW = suffixSum[idx];
if (totalW >= mid) {
low = mid + 1;
} else {
high = mid;
}
}
System.out.println(low - 1);
}
}
// 实现bisect_left功能：找到第一个大于等于target的元素索引
private static int bisectLeft(int[] arr, int target) {
int low = 0, high = arr.length;
while (low < high) {
int mid = (low + high) / 2;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
Python：
import bisect T = int(input().strip()) for _ in range(T): n = int(input().strip()) a_list = list(map(int, input().split())) w_list = list(map(int, input().split())) if n == 0: print(0) continue papers = list(zip(a_list, w_list)) papers.sort(key=lambda x: x[0]) a_sorted = [p[0] for p in papers] w_sorted = [p[1] for p in papers] suffix_sum = [0] * (n + 1) for i in range(n - 1, -1, -1): suffix_sum[i] = suffix_sum[i + 1] + w_sorted[i] max_a = a_sorted[-1] if n > 0 else 0 total_weight = suffix_sum[0] high_bound = min(max_a, total_weight) + 1 low, high = 0, high_bound while low < high: mid = (low + high) // 2 idx = bisect.bisect_left(a_sorted, mid) total_w = suffix_sum[idx] if total_w >= mid: low = mid + 1 else: high = mid print(low - 1)
第二题
给定一个正整数 n，一个长度为 n 的排列 p 是由 {1,2,…,n} 这 n 个整数按任意顺序组成的数组，其中每个整数恰好出现一次；我们定义该排列的代价为满足 pᵢ × pᵢ₊₁ 是完全平方数的索引 i 的个数（1 ≤ i < n）；请你构造一个排列 p，使其代价最大。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T（1 ≤ T ≤ 10⁴），表示测试用例数； 此后 T 行，每行输入一个整数 n（2 ≤ n ≤ 2×10⁵），表示排列的长度； 此外，保证所有测试用例的 n 之和不超过 2×10⁵。
输出描述
对于每组测试数据，新起一行，输出一个长度为 n 的排列 p 为最大代价的排列。 如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
样例输入
2
5
10
样例输出
2 3 1 4 5
10 7 6 1 4 9 2 8 3 5
参考题解
预处理核计算：使用筛法预处理每个数的最小质因数，然后计算每个数的核。核是通过分解质因数后，保留指数为奇数的质因数的乘积得到的。分组数字：对于每个测试用例，将1到n的数字按核分组。构造排列：将各组按核的升序排列，组内数字也按升序排列，以确保相同核的数字连续放置，从而最大化相邻对乘积为完全平方数的数量。
C++：
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
const int N_MAX = 200000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 计算最小素因子（sieve of Eratosthenes变体）
vector<int> min_prime(N_MAX + 1);
for (int i = 0; i <= N_MAX; ++i) {
min_prime[i] = i;
}
int sqrt_n = sqrt(N_MAX);
for (int i = 2; i <= sqrt_n; ++i) {
if (min_prime[i] == i) { // i是素数
for (int j = i * i; j <= N_MAX; j += i) {
if (min_prime[j] == j) {
min_prime[j] = i;
}
}
}
}
// 计算core数组：core[i]是i的所有出现奇数次的质因子的乘积
vector<int> core(N_MAX + 1);
core[1] = 1; // 1的core值为1
for (int i = 2; i <= N_MAX; ++i) {
int current = i
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
