PAT甲级1106.

目录

A1106

题目

样例

输入:

10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0

输出:

1.8362 2

思路和坑点

　　树的遍历，为了得到最低的加个，也就意味着零售商所在的层数最低，因此使用层序遍历，查找并统计层数最小的零售商所在的层数，并统计个数，如果不习惯使用变量来控制层数，可以直接在结点内部定义layer成员记录所在的层数。

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;                 //价格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("%.4f 1",p);
        return 0;
    }
    for(int i=0;i<n;i++){                    //读入数据并建树 
        int num;
        scanf("%d",&num);
        if(num){
            for(int j=0;j<num;j++){
                int temp;
                scanf("%d",&temp);
                T[i].child.push_back(temp);
                T[i].tag=false;             //如果有孩子，则修改标记不是零售商 
            }
        }
    }
    int minlayer=MAXN;                      //用于记录叶子结点（零售商）所在的最小层数 
    int cnt=1;                              //记录所求零售商的个数 
    queue<int> q;
    q.push(0);
    T[0].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;      //当前结点的孩子所在的层数为当前结点的层数+1 
            q.push(k);
        }
        if(T[now].tag==true){               //如果是零售商 
            if(T[now].layer<minlayer){      //如果有更小的层数的cnt重置为1 
                minlayer=T[now].layer;
                cnt=1;
            }
            else if(T[now].layer==minlayer) //如果于最小的层数相同，cnt加一 
                cnt++;
            
        }
    }
    printf("%.4f %d",p*pow(1.0+r/100,minlayer),cnt);
    return 0;    
}