[PAT解题报告] Total Sales of Supply Chain
给了经销商,零售商,供应商的关系,其实就是一棵有根树,根节点售价已知,每下一层售价增加r%,这样我们可以知道每个叶节点(供应商)的售价,dfs即可。又知道每个叶节点要卖多少,所以乘一下累加就能得到最终总的收入。 我没有区分叶节点和中间节点,而是用了一个数组a,表示每个节点要卖多少,事实上非叶节点这个值是0,所以累加到总和叶没关系。

代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

const int N = 100005;
vector<int> con[N];
int a[N];
double p[N],total,r;

void dfs(int father,int x) {
    if (father >= 0) {
        p[x] = p[father] * r;
    }
    total += p[x] * a[x];
    for (int i = 0; i < con[x].size(); ++i) {
        dfs(x, con[x][i]);
    }
}

int main() {
int n;
    scanf("%d%lf%lf",&n,p,&r);
    r = 1. + r / 100.;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d",&x);
        if (x == 0) {
            scanf("%d",&a[i]);
        }
        else {
            for (;x;--x) {
                int y;
                scanf("%d",&y);
                con[i].push_back(y);
            }
        }
    }    
    dfs(-1, 0);
    printf("%.1lf\n",total);
    return 0;
}

原题链接: http://www.patest.cn/contests/pat-a-practise/1079

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议