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

题目粗心：

给出一颗销售供给树, 根结点为 0, 在树根处售价为 P, 而后从根节点开始每往子节点走一层就, 该层的货物的价格就会在上一层的价格上减少 r%, 要求取得叶子结点最低售价以及最低售价的个数。

算法思路：

此题实质上考查的是树的遍历，该树是由供应商作为根节点，经销商作为子节点，零售商作为叶子节点组成。想要求叶子节点的最低售价及其个数，只需要求出叶子节点的售价，为此，咱们只须要从根节点遍历该树，计算所有节点的售价，这样在遍历到叶子节点的时候就能够间接统计最低售价及其个数。应用先序遍历或者层序遍历都是能够的，这里采纳了先序遍历的办法，代码如下所示：

double lowestPrice = 10000000000.0;
int numOflowestPrice = 0;

void preTraverse(int root,double r){if(node[root].child.empty()){
        // 零售商，叶子节点
        if(lowestPrice>node[root].price){lowestPrice = node[root].price;
            numOflowestPrice = 1;
        } else if(lowestPrice==node[root].price){++numOflowestPrice;}
    }
    double distributorPrice = node[root].price*(1+r/100);
    for(auto &item:node[root].child){node[item].price = distributorPrice;
        preTraverse(item,r);
    }
}

提交后果：

AC 代码：

#include <cstdio>
#include <vector>

using namespace std;

struct Node{
    vector<int> child;
    double price;
}node[100005];

double lowestPrice = 10000000000.0;
int numOflowestPrice = 0;

void preTraverse(int root,double r){if(node[root].child.empty()){
        // 零售商，叶子节点
        if(lowestPrice>node[root].price){lowestPrice = node[root].price;
            numOflowestPrice = 1;
        } else if(lowestPrice==node[root].price){++numOflowestPrice;}
    }
    double distributorPrice = node[root].price*(1+r/100);
    for(auto &item:node[root].child){node[item].price = distributorPrice;
        preTraverse(item,r);
    }
}

int main()
{
    int N;
    double P,r;// 供应链总人数
    scanf("%d %lf %lf",&N,&P,&r);
    for (int i = 0; i < N; ++i) {
        int K;
        scanf("%d",&K);
        if(i==0){
            // 供应商
            node[i].price = P;
        }
        if(K!=0){
            // 经销商，非叶节点
            int child;
            for (int j = 0; j < K; ++j) {scanf("%d",&child);
                node[i].child.push_back(child);
            }
        }
    }
    preTraverse(0,r);
    printf("%.4lf %d",lowestPrice,numOflowestPrice);
    return 0;
}