首页 > 试题广场 >

算法交流群

[编程题]算法交流群

热度指数：1772 时间限制：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个元素按顺序代表每个人产生的问题等级

算法知识视频讲解

积极的防守者

发表于 2020-02-10 23:04:20

普通解法除了群主牛牛，每个群友都有一个等级大于他的人作为朋友，那么最终是一个以牛牛为根的树。所以对于每个群友，一直往上找到第一个等级足够处理这个群友产生的问题上级，并统计答案。当这个树是一个链的时候，最差时间复杂度为只用到少量中间变量存储计算值，空间复杂度 vector<int&am 展开全文

Maokt

发表于 2021-08-03 18:08:42

算法思想一：普通解法解题思路：除了群主牛牛，每个群友都有一个等级大于他的人作为朋友，那么最终是一个以牛牛为根的树。所以对于每个群友，一直往上找到第一个等级足够处理这个群友产生的问题上级，并统计答案。在此基础上加一个字典，缓存每个人i遇到等级v时候最终对应的解决人是谁，下次遇到展开全文

呆喵挠琴

发表于 2021-08-05 00:31:06

思路：题目的主要信息：题目较长，要记住的是每个人只能解决难度小于等于他自己能力的问题，自己解决不了的问题就要交给更厉害的朋友：已知的信息有群友数量n，群友i的等级a[i]，群友i的朋友p[i-1],每个人产生问题难度k[i]. 求解每个人解决的问题数量，每个人解决的问题包括自己的问题和别人的问展开全文

认认真真coding

发表于 2021-08-08 13:56:05

题目描述牛牛有一个算法交流群，它是这个群的群主，也是这个群实力最强的人。算法交流群里一共有n个人，每个人都有一个等级ai表示它能解决难度小于等于ai的算法问题。除了牛牛以外，群里的每个编号为i的人都在群里有一个等级比他高的朋友编号为pi。群友 i 会解决那些他产生和接收的等级小于等于ai的问题，展开全文

ZhongHaoWang

发表于 2021-08-28 22:14:50

根据题意,我们可以建立一个有向无环图,并统计其入度,之后在图上进行拓扑排序,每次当我们遍历到一个节点时,判断其是否可以解决自身产生的问题,同时我们记录每个成员当前所接受的其他问题,分别统计解决问题个数即可。 import collections class Solution: def sol 展开全文

摸鱼学大师

发表于 2021-08-04 16:42:35

思路：题目的主要信息：三个数组，a表示每个人能够解决的问题的最大等级（首位必然最大），p为除a的首位外每个人拥有的能比自己能够解决更大等级问题的朋友，自己不能解决的问题可以交给朋友，k表示每个人产生的问题等级。当某个人产生一个问题，自己能够解决就自己解决，自己不行就交给朋友，朋友不行再给朋友展开全文