PAT-ADVANCED1090——Highest Price in Supply Chain
我的PAT-ADVANCED代码仓:https://github.com/617076674/PAT-ADVANCED
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805376476626944
题目描述:
题目翻译:
1090 供应链中的最高价格
供应链是零售商,经销商和供应商构成的网络 - 每个人都参与将产品从供应商转移到客户。从一个根供应商开始,链上的每个人都以价格P从一个供应商处购买产品,并以高于P的r%的价格出售或分销它们。只有零售商才会面对客户。 假设供应链中的每个成员除了根供应商之外只有一个供应商,并且没有供应环。现在给定供应链,您需要给出所有零售商中的最高价格。
输入格式:
每个输入文件包含一个测试用例。在每个测试用例中,第一行包含3个正整数:N(<= 10 ^ 5),供应链中的总节点数(节点编号为0 ~ N - 1,根结点编号为0);P,代表商品的单位价格;以及r,代表每个经销商或零售商的价格增量百分比。下一行包含N个数字,每个数字Si代表了编号为i的经销商的供应商。根节点Sroot的供应商定义为-1。一行中的所有数字由一个空格分隔。
输出格式:
对每个测试用例,在一行中输出所有零售商中的最高价格,精确到2位小数,以及出售这个价格的零售商数目。两个数字间用一个空格分隔。题目保证这个价格不会超过10 ^ 10。
输入样例:
9 1.80 1.00
1 5 4 4 -1 4 5 3 6
输出样例:
1.85 2
知识点:树的深度优先遍历、树的广度优先遍历
思路一:深度优先遍历的同时记录节点的层级
时间复杂度和空间复杂度均是O(N)。
C++代码:
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct node{
vector<int> child;
};
int N;
double P;
double r;
node Node[100000];
int countLevel[100000] = {0}; //第i层有countLevel[i]个叶子节点
void dfs(int nowVisit, int level);
int main(){
cin >> N >> P >> r;
int num;
int root;
for(int i = 0; i < N; i++){
cin >> num;
if(num == -1){
root = i;
continue;
}
Node[num].child.push_back(i);
}
dfs(root, 0);
int maxLevel;
for(int i = N; i >= 0 ; i--){
if(countLevel[i] != 0){
maxLevel = i;
break;
}
}
printf("%.2lf %d\n", pow(1 + r / 100, maxLevel) * P, countLevel[maxLevel]);
return 0;
}
void dfs(int nowVisit, int level){
if(Node[nowVisit].child.size() == 0){
countLevel[level]++;
return;
}
for(int i = 0; i < Node[nowVisit].child.size(); i++){
dfs(Node[nowVisit].child[i], level + 1);
}
}
C++解题报告:
思路二:广度优先遍历的同时判别是否是叶子节点
时间复杂度和空间复杂度均是O(N)。
C++代码:
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
struct node{
int level;
vector<int> child;
};
int N;
double P;
double r;
node Node[100000];
void bfs(int nowVisit);
int main(){
cin >> N >> P >> r;
int num;
int root;
for(int i = 0; i < N; i++){
cin >> num;
if(num == -1){
root = i;
continue;
}
Node[num].child.push_back(i);
}
bfs(root);
int maxLevel = 0;
for(int i = 0; i < N ; i++){
if(Node[i].level > maxLevel){
maxLevel = Node[i].level;
}
}
int countMaxLevel = 0;
for(int i = 0; i < N; i++){
if(Node[i].level == maxLevel){
countMaxLevel++;
}
}
printf("%.2lf %d\n", pow(1 + r / 100, maxLevel) * P, countMaxLevel);
return 0;
}
void bfs(int nowVisit){
queue<int> q;
Node[nowVisit].level = 0;
q.push(nowVisit);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = 0; i < Node[now].child.size(); i++){
Node[Node[now].child[i]].level = Node[now].level + 1;
q.push(Node[now].child[i]);
}
}
}
C++解题报告: