老师布置了 n 个题目,每个题目都有相应的分数及截止日期。各个题目的分 数及截止日期可能并不相同。对某题目而言,如果在该题目的截止日期前完成 则可获得对应的分数,否则无法得分。假设每个题目均需要花费一天的时间来 完成,这期间无法完成其他题目。请你设计算法指定题目的完成计划,从而使 总的得分最大。下面给出一个包含了 7 个题目及相应的分数、截止日期的实 例: 题目 1 2 3 4 5 6 7 截止日 期(天) 1 1 3 3 2 2 4 分数 6 7 2 1 4 5 1 要求:(1)用贪心算法设计并编写求解该问题的算法(7 分) (2)给出该算法的时间复杂度(3 分)
时间: 2023-06-11 17:06:28 浏览: 110
(1) 算法思路:
首先将所有的题目按照截止日期从早到晚排序,然后从前往后依次选择可以在截止日期前完成的题目,并计算得分。如果当前题目无法完成,则跳过该题目,继续选择下一个题目。直到无法选择任何一个题目为止,输出最大得分。
(2) 时间复杂度:
将题目按照截止日期排序的时间复杂度为 O(nlogn),从前往后扫描每个题目的时间复杂度为 O(n),故算法的总时间复杂度为 O(nlogn+n)=O(nlogn)。
(3) 算法实现:
```python
def max_score(n, ddl, scores):
# 将题目按照截止日期从早到晚排序
tasks = sorted(zip(ddl, scores))
# 初始化当前时间和总得分
curr_time = 0
total_score = 0
# 依次选择可以完成的题目并计算得分
for task in tasks:
if curr_time + 1 <= task[0]:
total_score += task[1]
curr_time += 1
return total_score
```
其中,n 是题目的数量,ddl 是一个长度为 n 的列表,表示每个题目的截止日期,scores 是一个长度为 n 的列表,表示每个题目对应的分数。函数返回值为最大得分。
相关问题
某学科老师布置了n个题目,每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言,如果在该题目的截止日期前完成则可获得对应的分数,否则无法得分。假设每个题目均需要花费一天
### 回答1:
时间完成,求最大得分。
解题思路:
首先,我们需要将所有题目按照截止日期从小到大排序,这样可以保证我们在做题时不会错过任何一个截止日期。
然后,我们从第一个题目开始做起,如果在该题目的截止日期前完成,则将该题目的分数加入总得分中;否则,直接跳过该题目。
最后,返回总得分即可。
代码实现:
假设题目的信息存储在一个列表中,每个元素包含题目的分数和截止日期,如下所示:
题目信息 = [(10, 3), (20, 5), (30, 1), (40, 4)]
其中,(10, 3)表示第一道题目的分数为10,截止日期为3天后。
代码如下:
def 最大得分(题目信息):
# 将题目按照截止日期从小到大排序
题目信息 = sorted(题目信息, key=lambda x: x[1])
# 初始化总得分和当前时间
总得分 = 0
当前时间 = 0
# 遍历每个题目
for 分数, 截止日期 in 题目信息:
# 如果当前时间加上1天小于等于截止日期,则可以完成该题目
if 当前时间 + 1 <= 截止日期:
总得分 += 分数
当前时间 += 1
# 返回总得分
return 总得分
# 测试
题目信息 = [(10, 3), (20, 5), (30, 1), (40, 4)]
print(最大得分(题目信息)) # 输出:70
说明:按照上述题目信息,我们可以先完成第三道题目(截止日期为1),获得30分;然后完成第一道题目(截止日期为3),获得10分;接着完成第四道题目(截止日期为4),获得40分;最后,由于第二道题目的截止日期为5,已经超过了总共可用的时间,因此无法得分。因此,最大得分为70分。
### 回答2:
假设你是一名学生,面对老师布置的n个题目,你要怎样制定学习计划呢?
首先,你需要列出所有题目的名称、对应分数和截止日期,以便于你对学习任务的全面把握。然后,你可以将这些题目按照截止日期进行排序,然后计算出每个题目距离当前时间的天数,这样你就能够知道哪个题目应该优先完成。
其次,你需要给每个题目安排一个具体的学习时间。假设你有50天时间来完成这些题目,那么你可以将每个题目与截止日期的差值除以题目分数,得到一个“每分需要的天数”,然后根据这个数据对题目进行排序。这个方法可以帮助你优先完成所占比重大的题目,以最大化你的得分。
最后,你需要根据你的学习进度来动态调整学习计划。如果你发现完成某个题目需要更多时间,那么就需要从其他题目中挤出一些时间,或者向老师请假请求额外时间。而如果你发现自己学习速度很快,可以提前完成某个题目,那么就可以把剩下的时间用来复习和做其他题目。
在制定学习计划的过程中,你需要考虑到自己的学习效率、时间安排合理性以及各个题目的分数及截止日期等因素。只有在全面考虑这些因素的基础上,你才能够制定出一份科学的学习计划,使得自己能够高效地完成学习任务,取得最好的成绩。
### 回答3:
为了尽可能拿到更高的总分,我们需要一种策略来规划完成所有题目的时间。首先,我们需要计算出所有题目的最晚截止日期,并将其作为整个计划的截止日期。假设这个日期为D。然后,我们可以按照以下步骤来规划时间:
1. 计算出每个题目的“紧迫程度”,即在截止日期前完成该题目的时间距离。这可以通过用D减去该题目的截止日期得到。例如,如果D是10天后,某个题目的截止日期是5天后,则它的紧迫程度为5天。
2. 按照紧迫程度从大到小排列所有题目,然后依次完成它们。这意味着我们首先应该完成截止日期最近的题目,然后继续完成下一个截止日期最近的题目,以此类推。
通过这种方式,我们可以最大限度地利用时间,确保在所有截止日期之前完成所有题目。需要注意的是,如果两个题目的截止日期相同,则应根据它们的分数进行排列(分数越高越先完成)。
此外,如果任务时间短缺,我们可以做出一些权衡来提高总分。例如,我们可以考虑跳过一些分数较低的题目,以便将更多时间用于完成分数较高的题目。但是,这需要权衡和计算来确保最大化总分。
总之,制定一个合理的计划并按照它执行,可以帮助我们最大程度地利用时间,取得更好的成绩。同时,我们也需要根据实际情况灵活调整计划,并做出一些权衡来优化结果。
如何布置布局使得一个网页里面的许多按钮(每个按钮都有分组)的排布美观
在布置布局时,可以使用以下方法来使许多按钮的排布更美观:
1. 使用网格布局: 可以使用网格布局来将按钮按照一定的行列排布。这样,每个按钮都有自己的单元格,按钮之间的间隔也更加均匀。
2. 分组: 可以将按钮按照分组进行排布,这样每组按钮之间的间隔就更大,整体看起来也更美观。
3. 调整间隔: 可以通过调整按钮之间的间隔,使得整个布局看起来更加美观。
4. 使用边框: 可以使用边框将每组按钮分隔开来,这样每组按钮之间的间隔就更大,整体看起来也更美观。
5. 调整字体: 可以调整按钮上文字的字体,使得整个布局看起来更加美观。
6. 使用颜色: 可以使用不同的颜色将每组按钮区分开来,这样每组按钮之间的间隔就更大,整体看起来也更美观。