关于算法-数据结构:PAT甲级1090-Highest-Price-in-Supply-Chain

题目粗心：

给出一颗销售供给树, 根结点为 0, 在树根处售价为 P, 而后从根节点开始, 每一层的货物的价格就会在上一层的价格上减少 r%, 要求输入售价最高的零售商和其个数。

算法思路：

此题和 1079 是一样的题目，采纳树的遍历 (先序遍历或者层序遍历) 获取所有节点的售价，在遍历到叶子节点的时候就更新最高售价和对应的零售商的个数。因为给的是以后结点和其父亲的关系, 所以每次输出 parent 的时候, 就将其孩子结点增加其中 node[parent].child.push_back(i),
而后对于 parent==-1 的状况, 应用root=parent, 保留根节点地位

留神点：

• 1、尽量不要应用 float 保留数据。

提交后果：

AC 代码：

#include <cstdio>
#include <vector>

using namespace std;

struct Node{
    double price;// 以后结点的售价
    vector<int> child;
}node[100005];

double highest_price = -1 ;// 最高售价
int num;// 最高售价的零售商的个数
void preTraverse(int root,double r){if(node[root].child.empty()){
        // 零售商，取得最高售价
        if(highest_price<node[root].price){
            num = 1;
            highest_price = node[root].price;
        } else if(highest_price==node[root].price){++num;}
        return;
    }
    double distributor_price = node[root].price*(1+r/100);
    for (auto &item:node[root].child){node[item].price = distributor_price;
        preTraverse(item,r);
    }
}

int main()
{
    int N;// 供应链总人数
    double P,r;// 供应商的单价，增量
    scanf("%d %lf %lf",&N,&P,&r);
    int root,parent;
    for (int i = 0; i < N; ++i) {scanf("%d",&parent);
        if(parent==-1){
            // 以后节点为根节点, 保留地位和售价
            root = i;
            node[i].price = P;
        } else {
            // 保留父子关系
            node[parent].child.push_back(i);
        }
    }
    preTraverse(root,r);
    printf("%.2lf %d",highest_price,num);
    return 0;
}