2021年第2学期COMP3121/9101：作业2你有五个问题，总分100分；每个问题值20分。您应该在7月12日星期一之前提交您的解决方案。请不要等到最后一刻才提交您的工作-无论您是否遇到网络问题，我们都不会接受通过电子邮件发送的解决方案。还要严格按照有关如何提交解决方案的说明进行操作。您对每个问题的解决方案必须在单独的文件中提交。这个班级有1000多名学生，因此除了特殊考虑或ELS学生可以获得一周的延期外，没有任何例外。您的解决方案必须是键入的、机器可读的.pdf文件。所有提交的内容都将被检查是否存在抄袭！您将获得n首歌曲的序列，其中第i首歌曲时长为`i分钟。您想要将所有歌曲放入有序的CD系列（例如CD1、CD2、CD3、...CDk）中，其中每张CD可以容纳m分钟。此外，(a)歌曲必须按给定的顺序录制，歌曲1，歌曲2，..,歌曲n.(b)必须包括所有歌曲。(c)任何歌曲都不能跨CD。你的目标是确定如何将它们放在CD上，以尽量减少所需的CD数量。给出你能找到该问题最优解的最有效算法，证明该算法是正确的并分析其时间复杂度。有P个入门级职位空缺，第i个职位空缺仅接受技能水平小于或等于pi的工人。还有Q个高级职位空缺，其中第i个至少需要qi的技能水平。每个工人最多只能做一份工作，每个职位空缺只接受一个工人。你的任务是确定你可以在时间O(NlogN+PlogP+QlogQ)内分配给工作的最大工人数。一个城市被攻击了由N怪物并由i内的单个英雄防御S单位的初始强度。要杀死一个怪物，英雄必须消耗1ai个单位的力量；如果怪物i被成功杀死，英雄将获得giunits的力量。因此，如果英雄在对付怪物i之前的力量c≥ai他可以杀死怪物并且他最终会得到c?ai+gi单位的力量。请注意，对于某些怪物i，您可能有gi≥ai，但对于其他一些j，您可能有aj>gj。你有S和foreachi你有ai和gi。设计一个算法，确定如果英雄要杀死所有怪物，他可以按什么顺序与怪物战斗（如果有这样的顺序）。如果没有这样的排序，算法应该输出“没有这样的排序”。假设所有的值都是正整数。给你n叠积木。第i个堆栈包含hi>0个相同的块。您还可以移动任何i≤n吗？1从堆栈i到堆栈i+1的任意数量的块。设计一个算法以在O(n)时间内找出它是否可能能够使堆栈的大小严格增加。（例如，1、2、3、4是严格递增的，而1、2、2、3不是）。您的算法的输入是一个长度为n的数组A，使得A[i]=hi。请注意，并没有要求您实际移动块，只是确定是否存在此类移动。您有n个工作，每个工作需要一个单位的时间才能完成。工作i将提供gi的利润（gi>0)如果在时间ti或之前完成，其中ti是大于或等于1的任意整数。在任何时刻只能完成一个作业，并且作业必须从开始到结束连续完成。（注意：如果作业i没有被ti完成，那么调度它根本没有任何好处。所有作业都可以最早从时间0开始。）给出最有效的算法来找到使总利润最大化的调度。WX：代码帮助
