PAT-ADVANCED1079——Total Sales of Supply Chain
我的PAT-ADVANCED代码仓:https://github.com/617076674/PAT-ADVANCED
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805388447170560
题目描述:
题目翻译:
1079 供应链总销售额
供应链是零售商,经销商和供应商构成的网络 - 每个人都参与将产品从供应商转移到客户。从一个根供应商开始,链上的每个人都以价格P从一个供应商处购买产品,并以高于P的r%的价格出售或分销它们。只有零售商才会面对客户。 假设供应链中的每个成员除了根供应商之外只有一个供应商,并且没有供应环。现在给定供应链,您需要给出所有零售商中的最高价格。
输入格式:
每个输入文件包含一个测试用例。在每个测试用例中,第一行包含3个正整数:N(<= 10 ^ 5),供应链中的总节点数(节点编号为0 ~ N - 1,根结点编号为0);P,代表商品的单位价格;以及r,代表每个经销商或零售商的价格增量百分比。接下来的N行,每行以下述形式描述一个经销商或零售商:
Ki ID[1] ID[2] ... ID[Ki]
在第i行,Ki代表的是从供应点i进货的经销商或零售商数量,紧跟着的是这些经销商或零售商的ID。Kj等于0时,表示第j号节点是一个零售商,其后的数字代表该零售商卖出的商品总数。一行中的所有数字以一个空格分隔。
输出格式:
对每个测试用例,输出所有零售商的销售总额,结果精确到小数点后1位。题目保证这个数字不会超过10 ^ 10。
输入样例:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例:
42.4
知识点:树的深度优先遍历、树的广度优先遍历
思路一:深度优先遍历的同时记录节点的层级
用printf函数的格式化输出“%.1lf”,会自动帮我们四舍五入。
时间复杂度和空间复杂度均是O(N)。
C++代码:
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
struct node{
int sales;
vector<int> child;
};
int N;
double P;
double r;
node Node[100000];
double totalSales = 0.0;
void dfs(int nowVisit, int level);
int main(){
cin >> N >> P >> r;
int K, num;
for(int i = 0; i < N; i++){
cin >> K;
if(K == 0){
cin >> num;
Node[i].sales = num;
}else{
for(int j = 0; j < K; j++){
cin >> num;
Node[i].child.push_back(num);
}
}
}
dfs(0, 0);
printf("%.1lf\n", totalSales);
return 0;
}
void dfs(int nowVisit, int level){
if(Node[nowVisit].child.size() == 0){
totalSales += Node[nowVisit].sales * P * pow(1.0 + r / 100, 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<math.h>
#include<queue>
using namespace std;
struct node{
int sales;
int level;
vector<int> child;
};
int N;
double P;
double r;
node Node[100000];
double totalSales = 0.0;
void bfs(int nowVisit);
int main(){
cin >> N >> P >> r;
int K, num;
for(int i = 0; i < N; i++){
cin >> K;
if(K == 0){
cin >> num;
Node[i].sales = num;
}else{
for(int j = 0; j < K; j++){
cin >> num;
Node[i].child.push_back(num);
}
}
}
bfs(0);
printf("%.1lf\n", totalSales); //自动四舍五入
return 0;
}
void bfs(int nowVisit){
queue<int> q;
Node[nowVisit].level = 0;
q.push(nowVisit);
while(!q.empty()){
int now = q.front();
if(Node[now].child.size() == 0){
totalSales += Node[now].sales * P * pow(1.0 + r / 100, Node[now].level);
}
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]);
}
}
}
void dfs(int nowVisit, int level){
if(Node[nowVisit].child.size() == 0){
return;
}
for(int i = 0; i < Node[nowVisit].child.size(); i++){
dfs(Node[nowVisit].child[i], level + 1);
}
}
C++解题报告: