2836. 在传球游戏中最大化函数值

调试中...

题目描述

题解

提交记录

代码

测试用例

测试结果

2836. 在传球游戏中最大化函数值

困难

相关企业

提示

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家编号互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之和，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver^(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			2
1	2	1	3
2	1	0	3
3	0	2	5
4	2	1	6

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			4
1	4	3	7
2	3	2	9
3	2	1	10

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

1 <= receiver.length == n <= 10⁵
0 <= receiver[i] <= n - 1
1 <= k <= 10¹⁰

通过次数

3.4K

提交次数

8.2K

通过率

41.8%

相关企业

提示 1

We can solve the problem using binary lifting.

提示 2

For each player with id x and for every i in the range [0, ceil(log₂k)], we can determine the last receiver's id and compute the sum of player ids who receive the ball after 2ⁱ passes, starting from x.

提示 3

Let last_receiver[x][i] = the last receiver's id after 2ⁱ passes, and sum[x][i] = the sum of player ids who receive the ball after 2ⁱ passes. For all x in the range [0, n - 1], last_receiver[x][0] = receiver[x], and sum[x][0] = receiver[x].

提示 4

Then for i in range [1, ceil(log₂k)], last_receiver[x][i] = last_receiver[last_receiver[x][i - 1]][i - 1] and sum[x][i] = sum[x][i - 1] + sum[last_receiver[x][i - 1]][i - 1], for all x in the range [0, n - 1].

提示 5

Starting from each player id x, we can now go through the powers of 2 in the binary representation of k and make jumps corresponding to each power, using the pre-computed values, to compute f(x).

提示 6

The answer is the maximum f(x) from each player id.

相似题目

跳跃游戏 VI

中等

贡献者