PAT(树)——1090 Highest Price in Supply Chain (25 分)

1090 Highest Price in Supply Chain (25 分)
A supply chain is a network of retailers(零售商), distributors(经销商), and suppliers(供应商)-- everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the highest price we can expect from some retailers.

Input Specification:
Each input file contains one test case. For each case, The first line contains three positive numbers: N (≤10
​5
​​ ), the total number of the members in the supply chain (and hence they are numbered from 0 to N−1); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then the next line contains N numbers, each number S
​i
​​ is the index of the supplier for the i-th member. S
​root
​​ for the root supplier is defined to be −1. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in one line the highest price we can expect from some retailers, accurate up to 2 decimal places, and the number of retailers that sell at the highest price. There must be one space between the two numbers. It is guaranteed that the price will not exceed 10
​10
​​ .

Sample Input:
9 1.80 1.00
1 5 4 4 -1 4 5 3 6
Sample Output:
1.85 2

题目大意:

给出一颗供货商的树,每往下一级价格上涨r%,求售价最高的零售商及其个数。

题目解析:

结构体存储目标结点的等级和孩子节点,dfs从上往下遍历,再做统计。

具体代码:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct node{
	int level;
	vector<int> child;
}A[101000];
void dfs(int root){
	for(int i=0;i<A[root].child.size();i++){
		int child=A[root].child[i];
		A[child].level=A[root].level+1;
		dfs(child);
	}
}
int main()
{
    int n,root;
    double p,r;
    scanf("%d %lf %lf",&n,&p,&r);
    for(int i=0;i<n;i++){
    	int parent;
    	scanf("%d",&parent);
    	if(parent==-1){
    		root=i;
    		A[root].level=0;
		}else
    		A[parent].child.push_back(i);
	}
	dfs(root);
	int maxlevel=-1,maxnum=0;
	for(int i=0;i<n;i++){
		if(A[i].level>maxlevel){
			maxlevel=A[i].level;
			maxnum=1;
		}else if(A[i].level==maxlevel)
			maxnum++;
	}
	printf("%.2f %d",p*pow((r/100+1),maxlevel),maxnum);
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务