算法第3次作业
1 医院排队问题
在一个医院中，有
个病人排队等待就诊，医院每次只能接诊 人。每个病人有一个病情严重度 ，不同病人的病情严重度可以相同。 越大表示病情越严重，病情越严重的病人应当越优先就诊，形式化地说：对于任意两个病人 , ，如果接诊顺序 ，那么一定有 。同时，每个病人还需要一定的时间 来完成就诊。记每个病人在排队时的等待时间为 ，即从第一个人开始看病，到自己看完病为止的时间。 请你安排病人接诊的顺序，在关注病人病情严重程度的前提下最小化总的等待时间
。 例如，有
, , 号三位病人前来就诊， ，那么就诊顺序应该安排为 号 - 号 - 号，总等待时间为 。 请设计一个高效算法，描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。
- 分析：这是一个最优化队列问题。根据题目限制，病人病情严重程度具有排列的最高优先级，首先对
进行排序。剩余 个病人时， 病情相同的情况下，接诊病人 ，总等待时间增加 。因此，在病情相同的时候，应优先治疗就诊时间短的病人。因此，整体思路是以病情严重程度为高优先级标准，就诊时间为低优先级标准，同时对病人排序，获得接诊顺序 。按照接诊顺序即可获得最终的总等待时间。排序方式使用快排。 - 时间复杂度：平均复杂度
，最大复杂度 。 - 伪代码：
2 生产线规划问题
某制造公司拥有一条生产线，工作时每天可获得收益
元，初始资金为 元。若当前资金大于等于升级费用 元，公司可以选择对生产线进行升级。每次升级会使生产效率提高，每天生产可以带来额外收益 元，且升级可以叠加，也就是说在第 次升级后，生产一天的收益为 。但升级过程需要停产（包括升级当天） 天，期间无法产生收益。 在接下来的
天内，公司希望通过合理安排升级时机以最大化最终资金。 请设计一个高效的算法，规划生产线的策略，以在
天内最大化公司的最终资金。请描述算法的核心思想，给出算法伪代码并分析其时间复杂度。
- 分析：为达到最大收益，当资金达到
时，应判断是否升级。假设已经升级 次，剩余 天，则有如下情况： 时升级后收益为0，不应升级； 时，如果升级后收益（这里指仅进行这一次升级后预估的收益）大于等于升级前收益，即 ，则应当进行升级。如果剩余 天时可以升级但不升级，那么之后时间都不应进行升级，以剩余 天和剩余 天为例：剩余 天时升级最后 天收益至少为 ，剩余 天时升级最后 天收益至少为 。 - 时间复杂度：
。 - 伪代码：
3 分店选址问题
某奶茶品牌想在全国投资开分店来扩大规模提高影响力，通过向新老顾客发放问卷的形式调研产生了
个备选地址，并实地考察到了两组数据 和 ，其中 表示第 个备选地址的人流量， 表示在该地址开店所需的最低资金。由于当前总资金有限，该奶茶品牌希望根据这两组数据，从 个备选地址中挑选出 个组成最终分店名单，使得能够在满足以下约束条件的前提下尽可能降低总投资成本：
对每个被选中的地址，应当按照其人流量与其他
个被选中地址人流量的比例来投入资金。例如，在 的情况下，如果最终分店选址为 , , 三地，而这三地的人流量分别为 , , ，那么最终投入在 , , 三地资金比例应严格保证为 。 被选中的每个地址的投入资金都不得低于其所需的最低资金。
请设计一个算法求满足上述条件的前提下，该奶茶品牌需要投入的总资金的最小值。请描述算法的核心思想，给出算法伪代码并分析其时间复杂度。
- 分析：设有一挑选方案选中
个地址，序号为 ，令这些地址流量为 ，最终投入总资金最小时各地资金为 。则由于投资比例应与流量比例相同，所以存在 ，且 。那么最终投入的最小总资金为 ，问题便转化为求 的最小值。首先按照各备选地的 以小到大对原本的备选地址 进行排序。按照排好的顺序进行遍历，确定选择当前备选地 的情况下 的最小值。由于已经按照 排序，因此此时 。要获得选择当前备选地的最小值，只需要获得在它之前的 个人流量最小的备选地一同组成方案。对于遍历过程中当前备选地之前的 个人流量最小的备选地，可使用大顶堆进行动态维护以降低时间复杂度。 - 时间复杂度：平均复杂度
，最大复杂度 。 - 伪代码：
4 食物链计数问题
对于一个生态系统，存在一个食物网
，该食物网中有 个结点，捕食关系为二元组的集合 ，其中 表示 捕食 ，体现在食物网中为 指向 的一条有向边。保证该食物网中的任一结点都存在与之相连的边，且食物网中不存在环。 食物链是食物网中以一种生物为起点，另一种生物为终点的有向路径。极大食物链定义为：位于链条起点的是生产者，它们不捕食其他生物而是通过光合作用等方式获取能量，即该节点的入度为
；而位于链条终点的是顶级消费者，这类生物不再被其他生物所捕食，即该节点的出度为 。
例如：在图中的食物网中，极大食物链有
条，为： ； ； ； 。其他链均不是极大食物链。 请设计一个高效的算法统计该食物网中极大食物链的数量。请描述算法的核心思想，给出算法伪代码并分析其时间复杂度。
- 分析：这是一个有向图的遍历问题，由于要找到全部的极大食物链，需要遍历整张图，因此深度优先遍历和广度优先遍历的时间复杂度相同，选择使用深度优先遍历。首先应该构建整张有向图，对于每一个节点
，构建两个数组 和 ，分别代表有向边指向该节点的节点和该节点有向边指向的节点。找到 数组为空的节点，作为初始的节点。按照每个节点的出节点进行遍历，并更改访问数组，最终达到遍历全部图。 - 时间复杂度：
， 其中 代表集合的元素数量。 - 伪代码：
5 迷宫逃离问题
给定一个
的迷宫，其入口和出口分别为 和 （行列坐标都从 开始）。每个格子的状态用 表示，并存在两种取值：
= 0，表示这个格子是空格子，可以通过；
= 1，表示这个格子是障碍物，不可通过。 入口
和出口 均为空格子。在迷宫中可从某个格子 移动到与其相邻的空格子 ( , , , 其中之一，且需保证移动后的横坐标必须位于 之间，纵坐标必须位于 之间)，消耗体力为 。 现可将至多
个障碍物移除，使其对应的格子的变为空格子，移除障碍物不消耗体力。 例如：在图中所示的迷宫中，不移除障碍物（如图
）最小消耗的体力为 ；移除坐标 处的障碍物再移动（如图 ）最小消耗的体力为 。在本例中消耗的最小体力为 。
请在此基础上设计一个尽可能高效的算法，求出从入口
到出口 需消耗的最小体力，描述算法的核心思想，给出算法伪代码并分析其时间复杂度。
- 分析：本题是无向图的遍历问题。允许路径上至多一块存在
，在这些路径中寻找路径长度的最小值。因此，可以进行深度优先遍历搜寻图中全部符合条件的路径，并动态维护最小值。在搜寻过程中，可以传递当前经过障碍物数量，以减少遍历数量。 - 时间复杂度：
，由于 。 - 伪代码：