PAT 1079 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.

Input Specification:
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 jbeing 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.

Output Specification:
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 1010.

Sample Input:
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
Sample Output:
42.4

#include <cstdio>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;struct node{int data;vector<int> child;double amount;int level;
}; 
node* Node[100010];
node* newnode(int data){node* root =new node;root->data=data;root->child.clear();root->amount=0;root->level=-1;return root;
}
void level(int root){queue<int> q;q.push(root);Node[root]->level=0;while(!q.empty()){int now=q.front();q.pop();if(!Node[now]->child.empty()){for(int i=0;i<Node[now]->child.size();i++){int a=Node[now]->child[i];q.push(a);Node[a]->level=Node[now]->level+1;}}}
}
int main(){int n;double p,r;scanf("%d%lf%lf",&n,&p,&r);for(int i=0;i<n;i++){Node[i]=newnode(i);}for(int i=0;i<n;i++){int type;scanf("%d",&type);if(type==0){scanf("%lf",&Node[i]->amount);}else{for(int j=0;j<type;j++){int a;scanf("%d",&a);Node[i]->child.push_back(a);}}}level(0);queue<node* > q;q.push(Node[0]);double sum=0;while(!q.empty()){node* no=q.front();q.pop();if(!no->child.empty()){for(int i=0;i<no->child.size();i++){q.push(Node[no->child[i]]);}}else{double rate=1+(r/100);sum+=p*pow(rate,no->level)*no->amount;}}printf("%.1lf\n",sum);
}

这道题还是蛮简单的,就是我看到题目中说数据不超过1010,觉得肯定会有数据溢出的测试点,本想着看到错误再改代码的,结果直接通过了,也算是轻松吧!
后来查资料发现,double基本不会溢出,基本可以放心。
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/91369.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

应用层协议——TCP(上)

文章目录 1. TCP协议1.1 TCP协议段格式1.2 确认应答(ACK)机制1.3 16位窗口大小1.4 6位标志位1.4.1 TCP三次握手 1.5 确认应答(ACK)机制1.6 超时重传机制1.7 连接管理机制1.7.1 理解TIME_WAIT状态1.7.2 理解 CLOSE_WAIT 状态 1. TCP协议 TCP全称为传输控制协议&#xff0c;意思…

基于C#的无边框窗体阴影绘制方案 - 开源研究系列文章

今天介绍无边框窗体阴影绘制的内容。 上次有介绍使用双窗体的方法来显示阴影&#xff0c;这次介绍使用API函数来进行绘制。这里使用的是Windows API函数&#xff0c;操作系统的窗体也是用的这个来进行的绘制。 1、 项目目录&#xff1b; 下面是项目目录&#xff1b; 2、 函数介…

Kubernetes网络模型

Kubernetes 用来在集群上运行分布式系统。分布式系统的本质使得网络组件在 Kubernetes 中是至关重要也不可或缺的。理解 Kubernetes 的网络模型可以帮助你更好的在 Kubernetes 上运行、监控、诊断你的应用程序。 网络是一个很宽泛的领域&#xff0c;其中有许多成熟的技术。对于…

剑指offer-2.1数组

数组 数组可以说是最简单的一种数据结构&#xff0c;它占据一块连续的内存并按照顺序存储数据。创建数组时&#xff0c;我们需要首先指定数组的容量大小&#xff0c;然后根据大小分配内存。即使我们只在数组中存储一个数字&#xff0c;也需要为所有的数据预先分配内存。因此数…

C++ 之动态链接库DLL使用注意事项及C#调用详解

C 之动态链接库DLL使用注意事项及C#调用详解 有时候算法开发完成之后需要封装成动态链接库DLL来进行集成&#xff0c;一方面增加了算法or代码的复用或者广泛使用性&#xff0c;另一方面也起了保密的效果平时封装成DLL之后放到一台新的电脑上会出现问题&#xff0c;所以本文总结…

初识结构体

文章目录 目录1. 结构体类型的声明1.1 结构的基础知识1.2 结构的声明1.3 结构成员的类型1.4 结构体变量的定义和初始化 2. 结构体成员的访问3. 结构体传参 目录 结构体类型的声明结构体初始化结构体成员访问结构体传参 1. 结构体类型的声明 1.1 结构的基础知识 结构是一些值的…

发布属于自己的 npm 包

1 创建文件夹&#xff0c;并创建 index.js 在文件中声明函数&#xff0c;使用module.exports 导出 2 npm 初始化工具包&#xff0c;package.json 填写包的信息&#xff08;包的名字是唯一的&#xff09; npm init 可在这里写包的名字&#xff0c;或者一路按回车&#xff0c;后…

Postgresql 基础使用语法

1.数据类型 1.数字类型 类型 长度 说明 范围 与其他db比较 Smallint 2字节 小范围整数类型 32768到32767 integer 4字节 整数类型 2147483648到2147483647 bigint 8字节 大范围整数类型 -9233203685477808到9223203685477807 decimal 可变 用户指定 精度小…

【Linux初阶】system V消息队列 + system V信号量

文章目录 一、system V消息队列&#xff08;了解&#xff09;二、system V信号量&#xff08;了解&#xff09;1.信号量是什么2.临界资源和临界区3.互斥4.为什么要信号量 三、IPC资源的组织方式结语 一、system V消息队列&#xff08;了解&#xff09; 消息队列提供了一个从一…

MongoDB 简介

什么是MongoDB ? MongoDB 是由C语言编写的&#xff0c;是一个基于分布式文件存储的开源数据库系统。 在高负载的情况下&#xff0c;添加更多的节点&#xff0c;可以保证服务器性能。 MongoDB 旨在为WEB应用提供可扩展的高性能数据存储解决方案。 MongoDB 将数据存储为一个…

4、Rocketmq之存储原理

CommitLog ~ MappedFileQueue ~ MappedFile集合 正常情况下&#xff0c;RocketMQ支持消息体字节数最多为1个G。注意该消息体并不单单是消息体body。如果生产的消息其字节数超过1个G则该消息是无法被落盘处理的。因为没有一个MapperFile文件可以承载该消息所有的字节数。 1.All…

linux学习(自写shell)[11]

打印出提示信息获取用户键盘输入 cmd_line[NUM];用来保存完整的命令行 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/wait.h>#define NUM 1024 char cmd_line[NUM]; //shell int main() {wh…

Kali Linux是什么?它的主要用途是什么?

1. Kali Linux是什么&#xff1f; Kali Linux是一款基于Debian Linux的发行版&#xff0c;专注于网络安全和渗透测试。它由全球顶尖的安全专家和黑客社区维护开发&#xff0c;提供了丰富的工具和资源&#xff0c;用于测试网络、系统和应用程序的安全性。Kali Linux以其强大的功…

C#字符串占位符替换

using System;namespace myprog {class test{static void Main(string[] args){string str1 string.Format("{0}今年{1}岁&#xff0c;身高{2}cm&#xff0c;月收入{3}元&#xff1b;", "小李", 23, 177, 5000);Console.WriteLine(str1);Console.ReadKey(…

聊一下互联网开源变现

(点击即可收听) 互联网开源变现其实是指通过开源软件或者开放源代码的方式&#xff0c;实现收益或盈利。这种方式越来越被广泛应用于互联网行业 在互联网开源变现的模式中&#xff0c;最常见的方式是通过捐款、广告、付费支持或者授权等方式获利。 例如&#xff0c;有些开源软件…

轻量级自动化测试框架WebZ

一、什么是WebZ WebZ是我用Python写的“关键字驱动”的自动化测试框架&#xff0c;基于WebDriver。 设计该框架的初衷是&#xff1a;用自动化测试让测试人员从一些简单却重复的测试中解放出来。之所以用“关键字驱动”模式是因为我觉得这样能让测试人员&#xff08;测试执行人员…

MySQL — 索引

文章目录 索引索引结构 — B树与B树B树B树 聚簇索引与非聚簇索引聚簇索引非聚簇索引优缺点 覆盖索引与回表联合索引索引覆盖最左前缀匹配 索引 索引是对数据库表中一列或多列的值进行排序的一种结构。MySQL索引的建立对于MySQL的高效运行是很重要的&#xff0c;索引可以大大提…

剑指 Offer 40. 最小的k个数

题目描述 输入整数数组 arr &#xff0c;找出其中最小的 k 个数。例如&#xff0c;输入4、5、1、6、2、7、3、8这8个数字&#xff0c;则最小的4个数字是1、2、3、4。 示例 思路 方法1 采用未改进的快速排序 class Solution {public int[] getLeastNumbers(int[] arr, int k…

k8s ------存储卷(PV、PVC)

目录 一&#xff1a;为什么需要存储卷&#xff1f; 二&#xff1a;emptyDir存储卷 ​三&#xff1a;hostPath存储卷 四&#xff1a;nfs共享存储卷 五&#xff1a;PVC 和 PV 1、PVC 和 PV介绍 2、PV和PVC之间的相互作用遵循的生命周期 3、PV 的4 种状态 4、一个PV从创…