题解 | #算法交流群#

思路：

题目的主要信息：
题目较长，要记住的是每个人只能解决难度小于等于他自己能力的问题，自己解决不了的问题就要交给更厉害的朋友：

• 已知的信息有群友数量n，群友i的等级a[i]，群友i的朋友p[i-1],每个人产生问题难度k[i].
• 求解每个人解决的问题数量，每个人解决的问题包括自己的问题和别人的问题。

方法一：暴力法

具体做法：先计算自己能够解决的问题，然后再计算帮别人解决的问题数量，需要注意的是牛牛无法解决的问题就不再管了。由于牛牛没有朋友，所以p数组是不包含牛牛朋友信息的，且牛牛编号默认为1，因此编号为i的群友的朋友是p[i-1].
在此解法中，num为最终结果，编号为i的群友的解决问题数量为n[i-1]
代码：

class Solution {
public:
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        // write code here
        vector<int> num(n,0);//num[i]为编号为i的人解决的问题个数
        for(int i=0;i<n;i++)//计算自己能解决的问题数
        {
            if(k[i]<=a[i])//如果产生的问题可以自己解决；
            {
                num[i]++;
                continue;
            }
            //如果自己无法解决
            if(i==0)//牛牛无法解决他接收的问题则不管这个问题
            {
                continue;
            }
            int f = p[i-1];//编号为i的群友的朋友是p[i-1]
            while(f>=1)
            {
                if(k[i]<=a[f-1])
                {
                    num[f-1]++;
                    break;
                }else if(f>1){
                    f=p[f-2];
                }else if(f==1){//牛牛也无法解决问题，那么这个问题就跳过
                    break;
                }
            }
        }
        return num;
    }
};

复杂度分析：

• 时间复杂度： 最坏情况下只有牛牛或者牛牛都无法解决问题。
• 空间复杂度： 只用到了常数空间。

方法二：树二分法

具体做法：因为牛牛的编号是1，并且它等级最高且唯一，因此可以构造一颗以牛牛为根的树，其他群友可根据之间的朋友关系构造出结点的值大于它的子孙结点值的大根堆。
接下来看从根到一个结点的路径，整条路径上根结点值越大，越远离根结点，结点值越小，因此路径上的结点值是有序的，可以用二分法。
因为从根到一个结点的路径上，点的权值是越远离根结点，权值越小，因此满足二分性质。树上倍增求得每个点向上 层的祖先。例如，当结点u无法解决这个问题时，我们可以用f[u][i]表示结点u沿着路径向上跳 层可以到达的结点，在建树的时候就根据路径完善数组。
举例说明建立f数组：

代码：

class Solution {
public:
    void dfs(int u, vector<vector<int>>& child, vector<vector<int>>& f){ //建立树
        for(int i = 0; i < 19; i++) 
            f[u][i + 1] = f[f[u][i]][i];
        for(int i = 0; i < child[u].size(); i++)
            dfs(child[u][i], child, f); //递归
    }
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        vector<int> num(n, 0);
        vector<vector<int> > f(n + 1, vector<int>(20)); //最多2^19层
        vector<vector<int> > child(n + 1); //记录对于每个结点的子结点
        for(int i = 0; i < n-1 ; i++)//先根据p数组，建立直接联系
        {
            f[i + 2][0] = p[i];
            child[p[i]].push_back(i + 2);
        }
        dfs(1, child, f); //深度优先建树
        if(k[0] <= a[0])
        {
            num[0]++;
        }
        for(int i = 1; i < n; i++)
        { 
            if(k[i] <= a[i])//结点i可以自己解决问题
            { 
                num[i]++; 
                continue;
            }
            int u = i + 1;//编号为u
            for(int j = 18; j >= 0; j--)//向上二分查找
            { 
                if(f[u][j] == 0) //跨度太大了，需要调整j值
                {
                    continue;
                }
                int t = f[u][j]; 
                if(k[i] > a[t - 1]) 
                {
                    u = t;
                }
            }
            u = f[u][0];
            if(u == 0) //牛牛也不能解决问题
                continue;
            else num[u - 1]++; 
        }
        return num;
    }
};

复杂度分析：

• 时间复杂度：二分法的时间复杂度。
• 空间复杂度：建树的时候递归空间。