PAT甲级1079.

目录

A1079

题目

样例

输入:

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

输出:

42.4

思路和坑点

　　本题考查多叉树的层序遍历，对给出的结果建树。然后层序遍历，并记录层数，对于零售商来说，其销售额销售额=p*（1+r%）^layer,其中layer代表零售商结点所在的层数。（根结点的层数为0）

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                        //多叉树结点结构体 
    int tag;                                //-1表示不是零售商，不是-1则表示零售商货物储量 
    vector<int> child;                      //孩子数组 
}Node;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    double p,r;
    scanf("%d%lf%lf",&n,&p,&r);             //读入参数 
    r=1+r/100;                              //直接将r换算成价格p的倍数 
    vector<Node> v(n);
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        if(num==0) scanf("%d",&v[i].tag);   //如果是零售商读入货物储量 
        else{
            v[i].tag=-1;                    //如果不是零售商，标记为-1 
            for(int j=0;j<num;j++){         //读入其孩子序号 
                int temp; scanf("%d",&temp);
                v[i].child.push_back(temp);    
            }
        }
    } 
    queue<int> q;                           //使用队列进行层次遍历 
    int layer=0,last=0,tail=0;              //layer记录层数，last记录当前层的最后一个，tail用于在当前层结束后更新last 
    double sum=0;                           //统计总销售额 
    q.push(0);
    while(!q.empty()){
        int now=q.front();                  //从队列中读出一个元素 
        q.pop();
        int size=v[now].child.size();
        for(int i=0;i<size;i++){            //将孩子依次入队 
            q.push(v[now].child[i]);
            tail=v[now].child[i];
        }
        if(v[now].tag!=-1)                  //如果当前节点是零售商，累加销售额 
            sum+=v[now].tag*p*pow(r,layer);    
        if(now==last){                      //当前层结束后，层数增加，更新last 
            layer++;
            last=tail;
        }
    }
    printf("%.1f",sum);                     //输出结果 
    return 0;
}