PAT_A 1106. Lowest Price in Supply Chain (25)

2023-11-05 01:38
文章标签 25 pat chain supply 1106 lowest price

本文主要是介绍PAT_A 1106. Lowest Price in Supply Chain (25),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1106. Lowest Price in Supply Chain (25)

  • 题目信息
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 lowest price a customer can expect from some retailers.Input Specification:Each input file contains one test case. For each case, The first line contains three positive numbers: N (<=105), 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 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:Ki ID[1] ID[2] ... ID[Ki]where in the i-th line, Ki 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. Kj being 0 means that the j-th member is a retailer. All the numbers in a line are separated by a space.Output Specification:For each test case, print in one line the lowest price we can expect from some retailers, accurate up to 4 decimal places, and the number of retailers that sell at the lowest price. There must be one space between the two numbers. It is guaranteed that the all the prices will not exceed 1010.
Sample Input:10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0Sample Output:1.8362 2
  • 简述
    最终所求是一棵树的深度问题。题目很简单,但自己一直有一个检测点运行超时,想了很久。最终通过备忘录的方式解决,之前知道备忘录,但终于用上并深刻体会到了。以下有种方式会很耗时即 1->2->3->4 4->5 4->6 4->7 4->8 。如果直接用循环或者递归的计算深度的话,根据题目线性最多100000,就会变成100000*100000/4,从 O(n)变成了O(n2),再加上题目运行时间限制,很容易超时。
    教训 运行超时,建立备忘录(在设计时,就建立吧,如果内存够用)。
  • 代码一(AC)
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
int p[100005];
int d[100005];
vector<int> r;
int count=1;
int n; 
int deep(int site)
{if(site==0)return 0;int pa=p[site];//就差这一步,备忘录,减少运算//正是由于备忘录的存在,避免了重复计算,// 1->2->3->4   4->5 4->6 4->7 4->8//1-2-3-4这部分有原来每次都计算,现在只计算一遍,从O(n2)-->O(n)if(d[pa]==-1)return d[site]=deep(pa)+1;return d[site]=d[pa]+1;
}
int main()
{double price=0;double rate=0;memset(p,-1,sizeof(p));memset(d,-1,sizeof(d));cin>>n>>price>>rate;for(int i=0;i<n;i++){int tmp=0;cin>>tmp;if(tmp==0){r.push_back(i);}for(int j=0;j<tmp;j++){int rs=0;cin>>rs;p[rs]=i;}}int min=100005;for(int i=0;i<r.size();i++){int tmp=deep(r[i]);if(min>tmp){min=tmp;count=1;}else if(min==tmp)count++;}double minp=price*pow(1+rate/100,min);printf("%.4f %d\n",minp,count);return 0;
}
  • 代码二(递归比循环省地方)
//循环计算深度和最小数量的函数,挺长的
int getdeep()
{int size=r.size();//int min=size+1;这是错误的int min=100005;for(int i=0;i<size;i++){int tmp=r[i];int deep=0;//这费时了while(p[tmp]!=-1){deep++;tmp=p[tmp];}if(min>deep){min=deep;count=1;}else if(min==deep){count++;}}return min;
}
  • 代码三(用链表做,我自己疯了)
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int n; 
struct tree
{bool leave;tree*p;tree(){p=NULL;leave=false;}
};
int count=1;
int lowest(vector<tree*>&t,vector<int>&v)
{int size=v.size();int min=size;for(int i=0;i<size;i++){tree*tmp=t[i];if(tmp->leave==true){//计算量跟代码二的差不多,同样是多重计算树干,超时//但从代码量、简洁程度、安全程度、理解程度用数组的方式更好,建立备忘录也容易。这都是教训~~while(tmp->p!=NULL){v[i]++;tmp=tmp->p;}if(min>v[i]){min=v[i];count=1;} else if(min==v[i]){count++;}}}return min;
}
int main()
{int n=0;double price=0;double rate=0;vector<tree*>t;vector<int>v;cin>>n>>price>>rate;for(int i=0;i<n;i++){tree *tmp=new tree;t.push_back(tmp);v.push_back(0);}for(int i=0;i<n;i++){int tmp=0;int tmp2=0;cin>>tmp;tree*ttmp=t[i];if(tmp==0){t[i]->leave=true;continue;}for(int j=0;j<tmp;j++){int pos;cin>>pos;tree*tt=t[pos];tt->p=ttmp;}}int min=lowest(t,v);double minp=price*pow(1+rate/100,min);printf("%.4f ",minp);cout<<count<<endl;return 0;
}
还有,输出格式话使用的是c语言形势的,以后还是专门记以下iomap吧,不然有点不伦不类。

这篇关于PAT_A 1106. Lowest Price in Supply Chain (25)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/346526

相关文章

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]

Keysight U8031A DC power supply

Keysight U8031A DC power supply 文章目录 Keysight U8031A DC power supply前言电容充电⽰意图一、恒定电压操作二、恒定电流操作三、5v操作四、跟踪模式操作五、存储器操作六、对过电压保护编程七、对过电流保护编程八、锁键操作 前言 U8031A Power Supply 是一款具备前面板编程能力的三路输出电源。通过使

2025年25届计算机毕业设计:如何实现高校实验室Java SpringBoot教学管理系统

✍✍计算机毕业编程指导师** ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java、Python、微信小程序、大数据实战项目集 ⚡⚡文末获取源码 文章目录 ⚡⚡文末获取源码高校实验室教学管理系统-研究背景高校实验室教学管理系

webservice系列3---chain

本节摘要:本节主要介绍webservice的高级特性chain的开发和配置 1.引言       之前在上webservice系列2---javabean&handler中讲了handler的使用,当有多个handler的时候,难道我们要一个一个的在wsdd文件中配置,然后一个一个的引入到需要的webservice中码?of course ,no。Apache组织已经替我们考虑到了这种需求,ch

智力题:25匹马5条跑道找最快的3匹马,最少需要跑几次?

要找出25匹马中最快的3匹马,使用5条跑道,最少需要跑几次?我们可以通过逐步推理来解决这个问题。 第一步:分组比赛 首先,我们将25匹马分成5组,每组5匹马。每组进行一次比赛,这样我们就有5次比赛的结果。 组1:A1, A2, A3, A4, A5 组2:B1, B2, B3, B4, B5 组3:C1, C2, C3, C4, C5 组4:D1, D2, D3, D4, D5 组

芬兰手游业25年发展史

自2010年Rovio凭借《愤怒的小鸟》成功以来,芬兰的优秀开发者可以说是不断的引领手游潮流,有Frogmid、Seriously这样的小型团队,也有Supercell这样的世界收入冠军。除却收入之外,我们可以发现芬兰开发商的手游绝大多数都是具有独特创意的。 为什么芬兰手游业可以具有如此之大的竞争优势?其他人想要赶上应该怎么做?这个答案从来都不是能够简单作答的,因为它根植于芬兰的行业发展史,所以

设计模式 -- 职责链模式(Chain of Responsibility Pattern)

1 问题引出 1.1 学校 OA 系统的采购审批项目 如果金额 小于等于 5000, 由教学主任审批 (0<=x<=5000)如果金额 小于等于 10000, 由院长审批 (5000<x<=10000)如果金额 小于等于 30000, 由副校长审批 (10000<x<=30000)如果金额 超过 30000 以上,有校长审批 ( 30000<x) 1.2 传统方式 传统方式是

图形API学习工程(25):实现法线贴图

工程GIT地址:https://gitee.com/yaksue/yaksue-graphics 目标 在《图形API学习工程(10):基础光照》中,我实现了最基础的光照,同时也表现了法线的作用。 在《图形API学习工程(11):使用纹理》中,工程已经能够加载纹理贴图。 这样,法线贴图 所需的准备已经完成,可以在工程里实现这个技术了。 (关于法线贴图的意义,可见上一篇博客《从“法线贴图的意义

Flink 原理与实现:Operator Chain原理

硬刚大数据系列文章链接: 2021年从零到大数据专家的学习指南(全面升级版) 2021年从零到大数据专家面试篇之Hadoop/HDFS/Yarn篇 2021年从零到大数据专家面试篇之SparkSQL篇 2021年从零到大数据专家面试篇之消息队列篇 2021年从零到大数据专家面试篇之Spark篇 2021年从零到大数据专家面试篇之Hbase篇

【简历】25届南京某一本JAVA简历:简历通过率还好,但是拿不到OFFER

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢,学校是一本。我们说上来先要定校招层次,这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历,一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复,要点对不对他不知道,就从这个角度来看,这位同学