Hard
题目描述
给你一个长度为 n 的整数数组 receiver 和一个整数 k。n 名玩家正在进行传球游戏。
你可以选择起始玩家 i。游戏按以下方式进行：玩家 i 将球传给玩家 receiver[i]，然后 receiver[i] 传给 receiver[receiver[i]]，依此类推，总共进行 k 次传球。游戏的得分是所有触球玩家的索引之和，包括重复，即 i + receiver[i] + receiver[receiver[i]] + ... + receiver^(k)[i]。
返回可能的最大得分。
注意：
receiver可能包含重复元素。receiver[i]可能等于i。
示例 1：
输入：receiver = [2,0,1], k = 4
输出：6
解释：从玩家 i = 2 开始，初始得分为 2：
- 第1次传球：2 -> 1，得分变为 3
- 第2次传球：1 -> 0，得分变为 3
- 第3次传球：0 -> 2，得分变为 5
- 第4次传球：2 -> 1，得分变为 6
示例 2：
输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：从玩家 i = 4 开始，初始得分为 4：
- 第1次传球：4 -> 3，得分变为 7
- 第2次传球：3 -> 2，得分变为 9
- 第3次传球：2 -> 1，得分变为 10
约束：
1 <= receiver.length == n <= 10^50 <= receiver[i] <= n - 11 <= k <= 10^10
解题思路
这道题的核心挑战是 k 的值可能非常大（最大 10^10），如果直接模拟每次传球会超时。我们需要使用**二进制提升（Binary Lifting）**技术来优化。
解题思路
基本思路：
对于每个起始玩家，我们需要计算经过 k 次传球后的总得分。由于 k 很大，直接模拟不可行。
二进制提升优化：
- 预处理每个玩家经过 2^i 次传球后的状态
- 对于任意的
k，将其表示为二进制，通过组合不同的 2^i 来快速计算结果
具体实现：
next[i][j]：从玩家i开始，经过 2^j 次传球后到达的玩家sum[i][j]：从玩家i开始，经过 2^j 次传球过程中所有玩家索引的总和
状态转移：
- 初始状态：
next[i][0] = receiver[i]，sum[i][0] = receiver[i] - 递推关系：
next[i][j] = next[next[i][j-1]][j-1]sum[i][j] = sum[i][j-1] + sum[next[i][j-1]][j-1]
计算过程：
对于每个起始玩家，根据 k 的二进制表示，累加对应位为1的贡献，最终得到该起始点的总得分。
时间复杂度主要来自预处理阶段，为 O(n log k)，查询阶段为 O(log k)。
代码实现
class Solution {
public:
long long getMaxFunctionValue(vector<int>& receiver, long long k) {
int n = receiver.size();
int maxBit = 64; // log2(10^10) < 64
// next[i][j] = 从i开始经过2^j次传球后到达的玩家
// sum[i][j] = 从i开始经过2^j次传球过程中的索引和
vector<vector<int>> next(n, vector<int>(maxBit));
vector<vector<long long>> sum(n, vector<long long>(maxBit));
// 初始化
for (int i = 0; i < n; i++) {
next[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
// 二进制提升预处理
for (int j = 1; j < maxBit; j++) {
for (int i = 0; i < n; i++) {
next[i][j] = next[next[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[next[i][j-1]][j-1];
}
}
long long maxScore = 0;
// 尝试每个起始玩家
for (int start = 0; start < n; start++) {
long long score = start; // 起始玩家的索引
int current = start;
long long remaining = k;
// 根据k的二进制表示进行跳跃
for (int bit = 0; bit < maxBit && remaining > 0; bit++) {
if (remaining & (1LL << bit)) {
score += sum[current][bit];
current = next[current][bit];
remaining -= (1LL << bit);
}
}
maxScore = max(maxScore, score);
}
return maxScore;
}
};
class Solution:
def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
n = len(receiver)
max_bit = 64 # log2(10^10) < 64
# next[i][j] = 从i开始经过2^j次传球后到达的玩家
# sum[i][j] = 从i开始经过2^j次传球过程中的索引和
next_player = [[0] * max_bit for _ in range(n)]
sum_indices = [[0] * max_bit for _ in range(n)]
# 初始化
for i in range(n):
next_player[i][0] = receiver[i]
sum_indices[i][0] = receiver[i]
# 二进制提升预处理
for j in range(1, max_bit):
for i in range(n):
next_player[i][j] = next_player[next_player[i][j-1]][j-1]
sum_indices[i][j] = sum_indices[i][j-1] + sum_indices[next_player[i][j-1]][j-1]
max_score = 0
# 尝试每个起始玩家
for start in range(n):
score = start # 起始玩家的索引
current = start
remaining = k
# 根据k的二进制表示进行跳跃
bit = 0
while remaining > 0 and bit < max_bit:
if remaining & (1 << bit):
score += sum_indices[current][bit]
current = next_player[current][bit]
remaining -= (1 << bit)
bit += 1
max_score = max(max_score, score)
return max_score
public class Solution {
public long GetMaxFunctionValue(IList<int> receiver, long k) {
int n = receiver.Count;
int maxBit = 64; // log2(10^10) < 64
// next[i][j] = 从i开始经过2^j次传球后到达的玩家
// sum[i][j] = 从i开始经过2^j次传球过程中的索引和
int[,] next = new int[n, maxBit];
long[,] sum = new long[n, maxBit];
// 初始化
for (int i = 0; i < n; i++) {
next[i, 0] = receiver[i];
sum[i, 0] = receiver[i];
}
// 二进制提升预处理
for (int j = 1; j < maxBit; j++) {
for (int i = 0; i < n; i++) {
next[i, j] = next[next[i, j-1], j-1];
sum[i, j] = sum[i, j-1] + sum[next[i, j-1], j-1];
}
}
long maxScore = 0;
// 尝试每个起始玩家
for (int start = 0; start < n; start++) {
long score = start; // 起始玩家的索引
int current = start;
long remaining = k;
// 根据k的二进制表示进行跳跃
for (int bit = 0; bit < maxBit && remaining > 0; bit++) {
if ((remaining & (1L << bit)) != 0) {
score += sum[current, bit];
current = next[current, bit];
remaining -= (1L << bit);
}
}
maxScore = Math.Max(maxScore, score);
}
return maxScore;
}
}
/**
* @param {number[]} receiver
* @param {number} k
* @return {number}
*/
var getMaxFunctionValue = function(receiver, k) {
const n = receiver.length;
const maxBit = 64; // log2(10^10) < 64
// next[i][j] = 从i开始经过2^j次传球后到达的玩家
// sum[i][j] = 从i开始经过2^j次传球过程中的索引和
const next = Array(n).fill(null).map(() => Array(maxBit).fill(0));
const sum = Array(n).fill(null).map(() => Array(maxBit).fill(0));
// 初始化
for (let i = 0; i < n; i++) {
next[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
// 二进制提升预处理
for (let j = 1; j < maxBit; j++) {
for (let i = 0; i < n; i++) {
next[i][j] = next[next[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[next[i][j-1]][j-1];
}
}
let maxScore = 0;
// 尝试每个起始玩家
for (let start = 0; start < n; start++) {
let score = start; // 起始玩家的索引
let current = start;
let remaining = k;
// 根据k的二进制表示进行跳跃
for (let bit = 0; bit < maxBit && remaining > 0; bit++) {
if (remaining & (1n << BigInt(bit))) {
score += sum[current][bit];
current = next[current][bit];
remaining -= (1n << BigInt(bit));
}
}
maxScore = Math.max(maxScore, score);
}
return maxScore;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log k) | 预处理需要 O(n log k)，每个起始点计算需要 O(log k)，总共 n 个起始点 |
| 空间复杂度 | O(n log k) | 需要存储 next 和 sum 两个二维数组，每个大小为 n × log k |
相关题目
- . Jump Game VI (Medium)