华为4.12实习机试第三题求解题思路
3、水资源调度
一座山峰按高度分为N层,从高到低编号分别为0,1,……,N-1除最低层外每一层上都有一个蓄水池,通过若干管道将每一层蓄水池中的水输送至最低层的水库中,管道之间通过阀门连接(阀门总数为M),现要找到每一层中离水库最近的关键阀门。
某一层的关键阀门定义为从该层蓄水池流向水库的水要么经过该阀门目不全部流向更低层(不考虑水库层)关键阀门,或者不经过该阀门目必须经过更低层(不考虑水库层)的关键阀门。
即:第n(n 关键阀门有如下性质:
1.任何路径从蓄水池流向水库的水,都必须经过至少一个关键阀门;
2.关键阀门从底层向上层确定,每层只有至多一个关键阀门
3.如果一层中从蓄水池流向水库的水全部流经了更低层的关键阀门,则该层无关键阀门;
4.如果一层中有多个阀门符合要求,则更靠近水库的确定为关键阀门;
5.水库层无关键阀门。
输入
第一行:输入两个整数N和M,其分别表示层数与阀门总数。
如3,5代表共有3层,5个阀门。
第二行:输入M个数字表示ID为0到M-1的阀门所在层数,层数为递增顺序。
如 0 0 1 1 2代表编号为0-4的阀门所在层数。0,1阀门在第0层,2,3阀门在第1层,4号阀门在第2层。
接下来输入M行,第行中的第一个数字k;表示通过阀门i-1下一步可到达的阀门个数。该行后面的 ki个数字分别表示这些阀门的编号ID,若k;为0则表示下一步没有可到达的阀门。
如
2 1 2
1 3
1 3
1 4
0,
分别表示0号阀门有2个可流向的阀门分别为1号阀门和2号阀门:1号阀门有1个可流向的阀门为3号阀门:2号阀门有1个可流向的阀门为3号阀门:3号阀门有一个可流向的阀门为4号阀门;4号阀门没有可流向的阀门;
注:最后一层有且只有一个阀门连接到水库,不同层中水只能由高层流向低层,同一层中水只能由小ID的阀门流向大ID的阀门。每层的最小ID的阀门只能接收来自该层蓄水池的水。
其中,1≤M≤2000,1≤N≤200≤ki 点赞 回复 发布于 2023-10-10 16:23 陕西
一座山峰按高度分为N层,从高到低编号分别为0,1,……,N-1除最低层外每一层上都有一个蓄水池,通过若干管道将每一层蓄水池中的水输送至最低层的水库中,管道之间通过阀门连接(阀门总数为M),现要找到每一层中离水库最近的关键阀门。
某一层的关键阀门定义为从该层蓄水池流向水库的水要么经过该阀门目不全部流向更低层(不考虑水库层)关键阀门,或者不经过该阀门目必须经过更低层(不考虑水库层)的关键阀门。
即:第n(n
1.任何路径从蓄水池流向水库的水,都必须经过至少一个关键阀门;
2.关键阀门从底层向上层确定,每层只有至多一个关键阀门
3.如果一层中从蓄水池流向水库的水全部流经了更低层的关键阀门,则该层无关键阀门;
4.如果一层中有多个阀门符合要求,则更靠近水库的确定为关键阀门;
5.水库层无关键阀门。
输入
第一行:输入两个整数N和M,其分别表示层数与阀门总数。
如3,5代表共有3层,5个阀门。
第二行:输入M个数字表示ID为0到M-1的阀门所在层数,层数为递增顺序。
如 0 0 1 1 2代表编号为0-4的阀门所在层数。0,1阀门在第0层,2,3阀门在第1层,4号阀门在第2层。
接下来输入M行,第行中的第一个数字k;表示通过阀门i-1下一步可到达的阀门个数。该行后面的 ki个数字分别表示这些阀门的编号ID,若k;为0则表示下一步没有可到达的阀门。
如
2 1 2
1 3
1 3
1 4
0,
分别表示0号阀门有2个可流向的阀门分别为1号阀门和2号阀门:1号阀门有1个可流向的阀门为3号阀门:2号阀门有1个可流向的阀门为3号阀门:3号阀门有一个可流向的阀门为4号阀门;4号阀门没有可流向的阀门;
注:最后一层有且只有一个阀门连接到水库,不同层中水只能由高层流向低层,同一层中水只能由小ID的阀门流向大ID的阀门。每层的最小ID的阀门只能接收来自该层蓄水池的水。
其中,1≤M≤2000,1≤N≤200≤ki
全部评论
佬 请问这道题知道思路了吗
分享
相关推荐
点赞 评论 收藏
转发
点赞 评论 收藏
转发
03-20 12:29
门头沟学院 计算机类 点赞 评论 收藏
转发
全站热榜
正在热议
# 牛客帮帮团来啦!有问必答 #
668180次浏览 11092人参与
# 无实习如何秋招上岸 #
215579次浏览 3369人参与
# 如何写一份好简历 #
253768次浏览 3842人参与
# 2022届毕业生现状 #
313591次浏览 4386人参与
# Offer比较,你最看重什么? #
48712次浏览 476人参与
# 毕业后不工作的日子里我在做什么 #
50939次浏览 682人参与
# 租房前辈的忠告 #
31391次浏览 2038人参与
# 你的简历改到第几版了 #
296748次浏览 4488人参与
# 你会选择考研还是直接就业 #
73833次浏览 841人参与
# 硬件人的简历怎么写 #
76580次浏览 777人参与
# 华为开奖那些事 #
696115次浏览 5977人参与
# 简历中的项目经历要怎么写 #
423659次浏览 7215人参与
# 我的成功项目解析 #
80349次浏览 2346人参与
# 秋招开了,你想投哪些公司呢 #
115432次浏览 3234人参与
# 找工作中的意难平 #
184834次浏览 3346人参与
# 本周投递记录 #
194632次浏览 5021人参与
# 我想象的工作vs实际工作 #
90503次浏览 1527人参与
# 五一之后,实习真的很难找吗? #
17667次浏览 111人参与
# 如何一边实习一边秋招 #
244682次浏览 4587人参与
# 你投了多少份简历,才拿到offer? #
5514次浏览 60人参与