OJ的时候一道题出现了超时问题

Question

题目描述

个人使用BFS出现这个问题。。。百思不得其解，请指教
结果测评：

代码如下所示：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
using std::vector;
using std::queue;
const int maxn=100010;
struct node{
    double data;
    vector<int>child;
    int layer;
}Node[maxn];
int n;
double p,r;

bool cmp(node a,node b){
    return a.layer>b.layer;
}

void BFS(int x){
    int layer=-1;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        layer++;
        int length=q.size();
        for(int i=0;i<length;i++){
            int index=q.front();
            q.pop();
            Node[index].layer=layer;
            for(int j=0;j<Node[index].child.size();j++){
                q.push(Node[index].child[j]);
            }
        }
    }
}
int main(){
    int root;
    int mem;
    scanf("%d%lf%lf",&n,&p,&r);
    for(int i=0;i<n;i++){
        scanf("%d",&mem);
        if(mem!=-1){
            //如果不是根节点
            Node[mem].child.push_back(i);
        }else{
            root=i;
        }
    }
    BFS(root);
    sort(Node,Node+n,cmp);
    int layer=Node[0].layer;
    int sum=0;
    for(int i=0;i<n;i++){
        if(Node[i].layer==layer)
            sum++;
    }
    printf("%.2f %d",p*pow(1+r/100,layer),sum);
    system("pause");
    return 0;
}

Answer 1

思路

题意就是求一棵树的高度，只需要一次bfs即可。

时间复杂度为O(n)，这题n的范围是小于n<=10^5，可以通过这个题。

你的代码确实很乱，而且思路不够清晰，请对照我的代码，看我有哪些优化的地方。

有问题可以评论或私信。

AC代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
vector<int> G[maxn];

int lenth[maxn]; //根结点到每个节点的长度

int bfs(int root) {
    int maxTran = 0;
    memset(lenth, -1, sizeof(lenth));
    queue<int> Q;
    Q.push(root);
    lenth[root] = 0;
    while(!Q.empty()) {
        int supp = Q.front(); Q.pop();
        for(int i = 0; i < G[supp].size(); i++) {
            int buy = G[supp][i];
            lenth[buy] = lenth[supp] + 1;
            Q.push(buy);
            maxTran = max(maxTran, lenth[buy]);
        }
    }
    return maxTran;
}

int main() {
    int n;
    double p, r;
    while(scanf("%d %lf %lf", &n, &p, &r) == 3) {
        for(int i = 0; i < n; i++) {
            G[i].clear();
        }
        int supp, root;
        for(int i = 0; i < n; i++) {
            scanf("%d", &supp);
            if(supp != -1) {
                G[supp].push_back(i);
            } else {
                root = i;
            }
        }
        // 树的高度
        int maxTran = bfs(root);
        double highPrice = p;
        for(int i = 0; i < maxTran; i++) {
            highPrice *= (1 + r / 100);
        }
        // 计算取得最高price的人数
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(lenth[i] == maxTran) cnt++;
        }
        printf("%.2f %d\n", highPrice, cnt);
    }
    return 0;
}

Answer 2

给你几个建议吧
1、你这发代码，别人都不知道题目是啥，怎么看呢。
2、既然有ac和超时，那么可能程序能得到正确的结果，但是还需要优化。
3、BFS的盲目的，迭代次数多以后就很费时和费内存了。