4.21网易算法笔试第1题第2题解答

import heapq
n = int(input())
nums = list(map(int, input().split()))
def getRes(nums):
    heap = [-x for x in nums]
    heapq.heapify(heap)
    res = 0
    while len(heap) > 1:
            top = heap[0]
            average = -sum(heap) / len(heap)
            if average == -heap[0]:
                break
            while -top > average:
                heapq.heappop(heap)
                top = heap[0]
            res += 1
    return res
print(getRes(nums))

n = int(input())
nums = list(map(int, input().split()))
parent = list(map(int, input().split()))
union_set = [-1 for _ in range(len(nums))]
for i in range(len(parent)):
    union_set[i + 1] = parent[i]
def findfastparent(node):
    if union_set[node - 1] == - 1:
        return node
    if nums[union_set[node - 1] - 1] >= nums[node - 1]:
        return node
    else:
        node = union_set[node - 1]
        return findfastparent(node)
res = []
for i in range(len(nums)):
    ans = findfastparent(i + 1)
    print(ans)
    res.append(ans)
print(" ".join(res))