首页 > 试题广场 >

算法交流群

[编程题]算法交流群

热度指数：1771 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个算法交流群，它是这个群的群主，也是这个群实力最强的人。

算法交流群里一共有n个人，每个人都有一个等级 $a_i$ 表示它能解决难度小于等于 $a_i$ 的算法问题。

除了牛牛以外，群里的每个编号为i的人都在群里有一个等级比他高的朋友编号为 $p_i$ 。群友 i 会解决那些他产生和接收的等级小于等于 $a_i$ 的问题，并把解决不了的问题全部交给 $p_i$ 。

保证牛牛的编号为1。保证牛牛的等级全场唯一且全场最高。如果牛牛解决不了他接收的问题，他将不管这些问题。

这天群里的每个人都产生了一个问题，牛牛知道了每个人产生问题等级 $k_i$ ，他想知道群里的每个人在这天解决了多少问题。

示例1

输入

4,[4,3,2,1],[1,2,3],[1,2,3,4]

输出

[2,2,0,0]

说明

群里一共有4个人
4产生了等级为4的问题，4的能力值为1，无法解决，所以4号把这个问题交给了3号.4号解决问题个数为0
3号产生了等级为3的问题，接受到等级为4的问题。3号本身等级为2，无法解决这两个问题，于是把这两个问题交给了2，自身解决问题个数为0.
2号产生了等级为2的问题，接受到等级为3，4的两个问题。2号等级为3，解决了等级为2，3的问题，把等级为4的问题交给了1.自身解决问题个数为2
1号产生了等级为1的问题，接受到等级为4的问题。1号自身等级为4，解决了这两个问题。自身解决问题个数为2

备注:


输入的第一个参数为整数n，代表群人数
输入第二个参数为vector<int> a，包含n个元素，按顺序代表每个人的等级
输入的第二个参数为vector<int> p，包含n-1个元素，按顺序代表2,3,...n号群友会找谁寻求帮助
输入的第三个参数为vector<int> k，包含n个元素按顺序代表每个人产生的问题等级

算法知识视频讲解

Python

anonyy

普通解法上加一个字典，缓存每个人i遇到等级v时候最终对应的解决人是谁，下次遇到就不用递归去找了

class Solution:

def solve(self , n , a , p , k ):
res = [0]*n
dic ={}
for i,v in enumerate(k):
if a[i]>=v:
dic[(i,v)] = i
res[i]+=1
else:
t = i
while t!=0 and a[i]<v:
t = p[t-1] -1
if (t,v) in dic:
res[dic[(t,v)]]+=1
break
if a[t]>=v:
dic[(i,v)]=t
res[t]+=1
break
return res

编辑于 2021-03-10 17:41:16 回复(0)