解题思路: n个时段n个游戏,每个时段只能玩一个游戏,所以只需要给玩的游戏排个次序使总罚款最小。贪心点:按时段依次选择ddl(截止时间)最前的先玩,不着急的后玩,如果ddl相同则wi罚款多的先玩罚款少的后玩;如果该游戏已经过了ddl那肯定是要罚款的,但我们可以在done(已经完成且没有罚款的游戏的wi值
)找一下,看看能不能极限一换一找个最小的罚款;已经罚款的游戏可以直接舍弃排在最后玩,相当于不占用当前时段
注意事项:
参考代码:
Money = int(input()) N = int(input()) ddl = [int(i) for i in input().split()] wi = [int(i) for i in input().split()] list = [(ddl[i],wi[i]) for i in range(N)] list = sorted(list, key = lambda t:(t[0],-t[1])) done = [] # 已经完成且没有罚款的游戏的wi值 i = 0 # i指时段 while 1: i += 1 if len(list) == 0: break if list[0][0] >= i: # 未超时,不用罚款 done.append(list[0][1]) list.pop(0) else: # 已超时,要罚款 if list[0][1] > min(done): done.append(list[0][1]) list.pop(0) Money -= min(done) done.remove(min(done)) else: Money -= list[0][1] list.pop(0) i -= 1 # 已经罚款的游戏可以直接舍弃排在最后玩,相当于不占用当前时段 print(Money if Money>0 else 0)
0.0分
1 人评分