题目粗心:
给出一颗销售供给树,根结点为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;}