PAT甲级1090.

目录

A1090

题目

样例

输入:

9 1.80 1.00
1 5 4 4 -1 4 5 3 6

输出:

1.85 2

思路和坑点

　　多叉树的层序遍历，找到最大成熟，并统计最大层数的叶子节点个数，使用结构体数组的形式表示多叉树。使用队列进行层序遍历。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005 
typedef struct node{        //多叉树结点 
    int layer;              //结点层数 
    bool tag;               //零售商标记 ，默认都是零售商 ,如果有孩子则修改为false 
    vector<int> child;
    node(){
        tag=true;
    }
}Node;
Node T[MAXN]; 
int n;
double p,r;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%lf%lf",&n,&p,&r);
    if(n==1){                                   //特判 
        printf("%.2f 1",p);
        return 0;
    }
    int root;
    for(int i=0;i<n;i++){                    
        int num;
        scanf("%d",&num);
        if(num==-1)    root=i;                  //记录根 
        else{                                   //读入孩子 
            T[num].child.push_back(i);          //如果有孩子说明不是零售商，修改标记为false 
            T[num].tag=false; 
        } 
    }
    int maxlayer=0;                             //记录最大层数 
    int cnt=1; 
    queue<int> q;                               //层序遍历 
    q.push(root);
    T[root].layer=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();                                //当前结点的孩子入队，并且更新其层数 
        for(int i=0;i<T[now].child.size();i++){
            int k=T[now].child[i];
            T[k].layer=T[now].layer+1;
            q.push(k);
        }
        if(T[now].tag==true){ 
            if(T[now].layer>maxlayer){          //如果有更大层数，则更新maxlayer，并把cnt重置为1 
                maxlayer=T[now].layer;
                cnt=1;
            }
            else if(T[now].layer==maxlayer)     //如果和最大的层数相同，cnt加一 
                cnt++;
            
        }
    }
    printf("%.2f %d",p*pow(1.0+r/100,maxlayer),cnt);
    return 0;    
}