[PAT A1079]Total Sales of Supply Chain
题目描述
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. Only the retailers will face the customers. 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 total sales from all the retailers.
输入格式
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 their ID's are numbered from 0 to N?1, and the root supplier's ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:
K?i?? ID[1] ID[2] ... ID[K?i??]where in the i-th line, K?i?? is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID's of these distributors or retailers. K?j?? being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after K?j??. All the numbers in a line are separated by a space.
输出格式
For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed ???.
输入样例
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解析
1.题目大意：首先输入n,p,r，n表示有n个成员（n≤10^5），p表示产品的单价，r表示销售商以高于原价r%的价格销售产品；然后输入n行数据，每行第一个数表示该成员有的下家数量，然后依次输入它的下家编号；如果输入的第一个数是0，那就表示该成员没有下家，然后输入一个数，表示这个商家的存货量。每个商家将产品批发给它的下家，总会以高于他购进这批产品的r%购入，所有的商家都有共同的一个root商家
2.这题是树的问题，可以得知，只有叶子结点的商家是直接销售，所以我们要找到所有的叶子结点并计算，此外它的层数代表他这批产品经手的次数，根节点为0层。即如果一个叶子结点在第二层，那么他销售产品的总收入为“它的存货量volume”x"单价p"x“(1+r%)^2”，将所有计算结果加起来即可。
3.第一次的代码只得了20分，有两组数据时间复杂度超了。我的想法是每个结点记录他父亲结点的编号，然后回溯至根节点，计算层数，代码如下：
#include<iostream>
#include<cmath>
using namespace std;
struct node
{int parent = -1, level = 0;//默认父亲结点编号为-1，层数为0
};
const int maxn = 100010; //最大不超过10^5个结点
int n;
int main()
{double p, r;scanf("%d%lf%lf", &n, &p, &r);node tree[maxn];int volume[maxn] = { -1 }; //记录存货量，只有叶子结点不为负for (int i = 0; i < n; i++) {int t, temp;scanf("%d", &t);if (t == 0) {scanf("%d", &temp);volume[i] = temp;}else {for (int j = 0; j < t; j++) {scanf("%d", &temp);tree[temp].parent = i;}}}int root = -1;for (int i = 0; i < n; i++) { //找根结点if (tree[i].parent == -1) {root = i;break;}}for (int i = 0; i < n; i++) { //计算所有结点深度int j = i;while (tree[j].parent != -1) {j = tree[j].parent;tree[i].level++;}}double result = 0; for (int i = 0; i < n; i++) { //计算总收入if (volume[i] != -1) {result += volume[i] * p*pow(r / 100 + 1, tree[i].level);}}printf("%.1f", result);return 0;
}4.第二次改变了数据结构，使用vector存放子树编号，然后定义了一个notroot数组判断是否为根结点，便于找到根结点
5.注意有可能需要改“连接器->系统->堆栈保留大小”，不然有可能因为容量不够而出现异常，报错
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int maxn = 100010; //最大容量不超过10^5
struct node
{int data = -1; //容量默认为-1vector<int> childs; //子树数组
};
int n;
double p, r;
double result = 0;
node tree[maxn];
void traverse(int i, int level);
int main()
{bool notroot[maxn] = { false }; //用于寻找根结点scanf("%d %lf %lf", &n, &p, &r);for (int i = 0; i < n; i++) {int t, temp;scanf("%d", &t);if (t == 0) {scanf("%d", &temp);tree[i].data = temp;}else{for (int j = 0; j < t; j++) {scanf("%d", &temp);notroot[temp] = true;tree[i].childs.push_back(temp);}}}int root = -1; for (int i = 0; i < n; i++) { //寻找根结点if (notroot[i] == false) {root = i;break;}}traverse(root, 0);printf("%.1f", result);return 0;
}
void traverse(int i, int level) {if (i == -1) return;if (tree[i].data != -1) { //只有叶节点data才不为-1result += p * tree[i].data*pow(r / 100 + 1, level);}for (int j = 0; j < tree[i].childs.size(); j++) traverse(tree[i].childs[j], level + 1);
}