该题解采用复杂的方法处理球传递游戏问题。首先，创建一个数据结构记录每个玩家作为接球者的所有前驱，用于处理球的传递链。通过定义 FillNode 类来追踪传球过程中的累积分数以及其他元数据，然后实现一个 iterNode 函数来遍历传球链。主要的处理逻辑在 fill 函数中，该函数利用循环找到传球序列的开始和结束，并计算序列长度以及累积和，从而能够模拟整个传球过程并更新每个玩家的最终得分。最后，通过遍历所有可能的传球起始玩家来找到可以获得最大分数的起始玩家。
时间复杂度: O(n * k)
空间复杂度: O(n)
class Solution:
def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
n = len(receiver)
# 初始化每个玩家的前驱列表和初始分数数组
prevs = [[] for _ in range(n)]
res = [-1]*n
# 字典用于存储传球链的偏移量映射
offMap = {}
for i, ri in enumerate(receiver):
prevs[ri].append(i)
it1 = (i for i, (lst, v) in enumerate(zip(prevs, res)) if not lst and v < 0)
it2 = (i for i, v in enumerate(res) if v < 0)
class FillNode:
def __init__(self, i, accu=0, _next=None):
self.i = i
self.accu = accu
self.next = _next
self.pursue, self.pursueAccu = -1, 0
self.q = deque()
def iterNode(head):
node = head.next
while node:
yield node
node = node.next
def fill(prev, circleLen, circleSum, off, accus):
head = FillNode(-1)
head.next = FillNode(prev, prev)
head.next.prev = head
circles, r = divmod(k+1, circleLen)
circles *= circleSum
for rnd in count(1):
if not head.next: break
if rnd < k+1:
r -= 1
if r < 0:
circles -= circleSum
r += circleLen
delta = circles + accus[off+r] - accus[off]
for node in iterNode(head):
res[node.i] = node.accu + delta
elif rnd == k + 1:
for node in iterNode(head):
node.pursue = node.pursueAccu = prev
res[node.i] = node.accu
else:
for node in iterNode(head):
res[node.i] = node.accu - node.pursueAccu
node.pursue = node.q.popleft() if len(prevs[node.pursue]) > 1 else prevs[node.pursue][0]
node.pursueAccu += node.pursue
for node in iterNode(head):
ps = prevs[node.i]
if len(ps) == 1:
node.i = ps[0]
node.accu += node.i
else:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
for p in ps:
new = FillNode(p, node.accu + p, head.next)
if head.next:
head.next.prev = new
head.next = new
new.prev = head
new.q = deque(node.q)
new.q.append(p)
new.pursue = node.pursue
new.pursueAccu = node.pursueAccu
for i in chain(it1, it2):
offMap.clear()
accus = [0]
while offMap.get(i) is None:
offMap[i] = len(offMap)
accus.append(accus[-1]+i)
last, i = i, receiver[i]
circleLen = len(offMap) - offMap[i]
circles, r = divmod(k + 1, circleLen)
startOff = offMap[i]
circleSum = accus[-1] - accus[startOff]
circleTotal = circleSum * circles
for off in range(startOff, len(offMap)):
accus.append(accus[-1] + i)
res[i] = circleTotal + accus[off+r] - accus[off]
for prev in prevs[i]:
if prev != last:
fill(prev, circleLen, circleSum, off, accus)
last, i = i, receiver[i]
return max(res)