PAT-Highest Price in Supply Chain (25)

题目来源

Highest Price in Supply Chain (25)

题目描述点击链接自行查看

注意点

• 每次分销溢价 r% 不是 r
• 输出保留两位小数

思路简介

建树（我用的链式前向星，这里不介绍了，邻接表，邻接矩阵也可以） 树的高度-1就是溢价的次数 树的最后一层结点数就是价格最高的分销商数量 bfs遍历树，保存每层结点数即可

遇到的问题

代码

/**
* https://www.nowcoder.com/pat/5/problem/4316
* 建树+bfs
*/
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+8;
int head[N];
struct Edge{
int to,next;
}e[N];
int cnt=0;

void add(int u,int v){
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}

int n;
double p,r;

int input(){
memset(head,–1,sizeof(head));
cin>>n>>p>>r;
int root=0;
for(int i=0;i<n;++i){
int u;cin>>u;
if(u!=–1)
add(u,i);
else root=i;
}
return root;
}

double cal(double a,int k,double r){
for(int i=0;i<k;++i){
a*=r/100+1;
}
return a;
}

void solve(){
int root=input();

queue<int>q;
q.push(root);
int num=1,h=0,final_layer_num=0;

while(!q.empty()){
int u=q.front();
q.pop();num—;

//加结点
for(int i=head[u];i!=–1;i=e[i].next){
q.push(e[i].to);
}

if(!num){//说明遍历完了一层，此时队列中的元素个数即下一层的结点个数
num=q.size();
h++;
if(num)
final_layer_num=num;
}
}
cout<<fixed<<setprecision(2)<<cal(p,h–1,r)<<' '<<final_layer_num;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
int T=1;
//cin>>T;
while(T—){
solve();
}
return 0;
}