2023-05-10 21:49 西北工业大学 C++
关注
华为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
全部评论
offer门_
门头沟学院 算法工程师
佬 请问这道题知道思路了吗
相关推荐
投递小米集团等公司10个岗位 >
全站热榜
正在热议
# 25届秋招总结 #
302680次浏览 2685人参与
# 如果不工作真的会快乐吗 #
59443次浏览 519人参与
# 阿里云管培生offer #
17760次浏览 296人参与
# 地方国企笔面经互助 #
3870次浏览 11人参与
# 美团求职进展汇总 #
1327979次浏览 12451人参与
# 选完offer后，你后悔学本专业吗 #
20114次浏览 144人参与
# 百度开奖 #
163622次浏览 981人参与
# 正在实习的你，几点下班 #
52096次浏览 391人参与
# 国央企薪资爆料 #
8583次浏览 69人参与
# 如何一边实习一边秋招 #
992411次浏览 12640人参与
# 提前批简历挂麻了怎么办 #
146545次浏览 1948人参与
# 学历or实习经历，哪个更重要 #
51236次浏览 402人参与
# 海康威视求职进展汇总 #
399000次浏览 3406人参与
# 米哈游求职进展汇总 #
176048次浏览 1458人参与
# 求职遇到的搞笑事件 #
70887次浏览 577人参与
# 投递实习岗位前的准备 #
1179619次浏览 18397人参与
# 面试体验感最好的是哪家？ #
85140次浏览 846人参与
# 实习生应该准时下班吗 #
167478次浏览 1159人参与
# 得物求职进展汇总 #
66339次浏览 682人参与
# 网申一定要掌握的小技巧 #
5343次浏览 53人参与
# 招聘要求与实际实习内容不符怎么办 #
10308次浏览 273人参与
# 0offer是寒冬太冷还是我太菜 #
898785次浏览 8015人参与